Problem Statement

Given a stack of integers, write a function to sort the stack in ascending order using recursion. The sorted stack should have the smallest elements on the top. You are only allowed to use recursion and no additional data structures (like arrays or lists) for sorting.

Examples

Example 1:

Input:

    |  2  | <- Top element
    |  1  |
    |  3  |
    |  4  |
    |  0  |
    +-----+

Output:

    |  4  | <- Top element
    |  3  |
    |  2  |
    |  1  |
    |  0  |
    +-----+

Dry Run:

Initial Stack:

| -3 | <- Top Element
| 14 |
| 18 |
| -5 |
| 30 |

Unwinding Phase:

First call to sortStack on the initial stack:
    topElement = -1 is removed from the stack.

Second Call to sortStack (Stack = [14, 18, -5, 30]):
    topElement = 14 is removed.
    
Third Call to sortStack (Stack = [18, -5, 30]):
    topElement = 18 is removed.

Fourth Call to sortStack (Stack = [-5, 30]):
    topElement = -5 is removed.

Fifth Call to sortStack (Stack = [30]):
    topElement = 30 is removed.

Base Case: sortStack is called on an empty stack, so the function returns immediately.

Insertion Phase using SortedInsert:

Insert 30:

    The stack is empty, so 30 is directly pushed onto the stack.
    
    stack after this step:
    
    |  30  | <- Top of stack
    +------+

Insert -5:

    30 (top) is greater than -5.
    Pop 30 and recursively call sortedInsert with -5 on an empty stack.
    push -5 onto the stack and then push 30 back.
    
    stack after this step.
    
    |  30  | <- Top of stack
    |  -5  |
    +------+

Insert 18:

    30 (top) is greater than 18.
    Pop 30 and call sortedInsert with 18 on [-5].
    
    18 is greater than -5, so push 18 directly and then push 30 back.
    
    stack after this step:
    
    |  30  | <- Top of stack
    |  18  |
    |  -5  |
    +------+

Insert 14:

    30 (top) is greater than 14.
    Pop 30 and call sortedInsert with 14 on [-5, 18].
    18 (top) is greater than 14, so pop 18 and call
    sortedInsert with 14 on [-5].
    14 is greater than -5, so push 14 directly and then push
    back 18 and 30.
    
    stack after this step:
    
    |  30  | <- Top of stack
    |  18  |
    |  14  |
    |  -5  |
    +------+

Insert -3:

    30 (top) is greater than -3.
    Pop 30 and call sortedInsert with -3 on [-5, 14, 18].
    18 (top) is greater than -3, so pop 18 and call sortedInsert with
    -3 on [-5, 14].
    14 (top) is greater than -3, so pop 14 and call sortedInsert with
    -3 on [-5].
    -5 (top) is greater than -3, so pop -5 and call sortedInsert with
    -3 on empty stack.
    Push -3, then push back -5, 14, 18, and 30.
    
    stack after this step:
    
    |  30  | <- Top of stack
    |  18  |
    |  14  |
    |  -5  |
    |  -3  |
    +------+

Code:

#include <iostream>
#include <stack>
using namespace std;

// Helper function to insert an element into a sorted stack
void sortedInsert(stack<int>& s, int element) {
    // If stack is empty or top element is less than the element to be inserted
    if (s.empty() || element > s.top()) {
        s.push(element);
        return;
    }
    
    // Remove the top element
    int topElement = s.top();
    s.pop();
    
    // Recursive call to insert element in the sorted stack
    sortedInsert(s, element);
    
    // Push the top element back
    s.push(topElement);
}

// Function to sort the stack
void sortStack(stack<int>& s) {
    // Base case: if stack is empty
    if (s.empty()) {
        return;
    }
    
    // Remove the top element
    int topElement = s.top();
    s.pop();
    
    // Recursive call to sort the remaining stack
    sortStack(s);
    
    // Insert the top element back in the sorted stack
    sortedInsert(s, topElement);
}

// Helper function to print stack
void printStack(stack<int> s) {
    while (!s.empty()) {
        cout << s.top() << " ";
        s.pop();
    }
    cout << endl;
}

int main() {
    stack<int> s;
    s.push(30);
    s.push(-5);
    s.push(18);
    s.push(14);
    s.push(-3);

    cout << "Original Stack:" << endl;
    printStack(s);

    // Sort the stack
    sortStack(s);

    cout << "Sorted Stack:" << endl;
    printStack(s);

    return 0;
}

Complexity Analysis:

• Time Complexity: O(n^2)
  • Recursive calls in sortStack
    • For a stack of size n sortStack is called n times, each time removing the top element and reducing the problem size by 1.
    • Each call to sortStack is followed by a call to sortedInsert.
  • Recursive calls in sortedInsert:
    • When inserting an element back into the stack in the sorted position, sortedInsert may need to move elements out of the stack temporarily until it finds the correct position.
    • In the worst case, sortedInsert may be called recursively up to n times for each element being inserted back into the stack.
• Space Complexity: O(n)