Sort a Stack Using a Temporary Stack and Recursion

Sorting a stack means rearranging its elements so the largest sits on top and the smallest at the bottom, using only push(), pop(), peek(), and isEmpty().

No random access. No indexing. No auxiliary array. That is the constraint interviewers set when they ask this question, and it is what makes the problem interesting: you must sort a data structure that only lets you see one element at a time.

Two standard approaches exist. The first uses a second stack as temporary storage (iterative). The second uses the call stack itself as implicit storage (recursive). Both run in O(n²) worst-case time. The choice between them is about clarity and interview context, not performance.

The Constraint: Stack Operations Only

A stack is a LIFO (Last In, First Out) container. The only way to inspect an element is to pop everything above it. This restriction eliminates direct comparison between arbitrary pairs, which is why standard O(n log n) sorts (quicksort, mergesort) do not apply directly.

The allowed operations:

• push(x) — place x on top
• pop() — remove and return the top element
• peek() or top() — return the top element without removing it
• isEmpty() — check if the stack has zero elements

With just these four primitives, we need to produce a sorted stack. The trick in both methods is the same: find the correct position for each element by comparing against visible tops, shuttling elements between containers until the slot opens.

Method 1: Temporary Stack (Iterative)

The temporary-stack algorithm works by maintaining a sorted invariant on the second stack. Every element popped from the input is inserted at its correct position in tempStack.

Algorithm

• Create an empty tempStack.
• While inputStack is not empty:
  • Pop the top of inputStack into a variable called current.
  • While tempStack is not empty AND tempStack.top() > current: pop from tempStack and push back onto inputStack.
  • Push current onto tempStack.
• When done, tempStack holds all elements sorted with the largest on top.

Traced Walkthrough

Input stack (top to bottom): [34, 3, 31, 98, 92, 23]

• Step 1: Pop 34. tempStack is empty, push 34. tempStack: [34]
• Step 2: Pop 3. tempStack top is 34, and 34 > 3 is true, so pop 34 back to input. tempStack top is now empty. Push 3 to tempStack, then push 34 on top. tempStack: [34, 3]
• Step 3: Pop 31. tempStack top is 34, and 34 > 31 is true, so pop 34 back. tempStack top is now 3, and 3 > 31 is false. Push 31. Push 34 back on top. tempStack: [34, 31, 3]
• Step 4: Pop 98. tempStack top is 34, and 34 > 98 is false. Push 98 directly. tempStack: [98, 34, 31, 3]
• Step 5: Pop 92. tempStack top is 98, and 98 > 92 is true, so pop 98 back. tempStack top is 34, and 34 > 92 is false. Push 92, push 98 back. tempStack: [98, 92, 34, 31, 3]
• Step 6: Pop 23. tempStack top is 98, 98 > 23 true, pop back. Top 92, 92 > 23 true, pop back. Top 34, 34 > 23 true, pop back. Top 31, 31 > 23 true, pop back. Top 3, 3 > 23 false. Push 23. Push back 31, 34, 92, 98 (each re-inserted via subsequent iterations). tempStack: [98, 92, 34, 31, 23, 3]

Final sorted stack (top to bottom): [98, 92, 34, 31, 23, 3].

C++ Implementation

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

stack<int> sortStack(stack<int> input) {
    stack<int> tempStack;

    while (!input.empty()) {
        int current = input.top();
        input.pop();

        while (!tempStack.empty() && tempStack.top() > current) {
            input.push(tempStack.top());
            tempStack.pop();
        }

        tempStack.push(current);
    }

    return tempStack;
}

int main() {
    stack<int> s;
    s.push(23); s.push(92); s.push(98);
    s.push(31); s.push(3); s.push(34);

    stack<int> sorted = sortStack(s);

    cout << "Sorted stack (top to bottom): ";
    while (!sorted.empty()) {
        cout << sorted.top() << " ";
        sorted.pop();
    }
    return 0;
}

Output: Sorted stack (top to bottom): 98 92 34 31 23 3

Python Implementation

def sort_stack(input_stack):
    temp_stack = []

    while input_stack:
        current = input_stack.pop()

        while temp_stack and temp_stack[-1] > current:
            input_stack.append(temp_stack.pop())

        temp_stack.append(current)

    return temp_stack

stack = [23, 92, 98, 31, 3, 34]
sorted_stack = sort_stack(stack)
print("Sorted stack (top to bottom):", sorted_stack[::-1])

Output: Sorted stack (top to bottom): [98, 92, 34, 31, 23, 3]

Method 2: Recursion (sortStack + insertSorted)

The recursive approach decomposes the problem into two sub-problems:

• sortStack(stack) — pop the top element, recursively sort the remaining stack, then insert the popped element at its sorted position.
• insertSorted(stack, element) — if the stack is empty or the element is greater than the top, push it. Otherwise, pop the top, recursively insert the element deeper, then push the popped value back.

Traced Walkthrough

Input stack (top to bottom): [34, 3, 31, 98, 92, 23]

sortStack pops 34, then calls itself on [3, 31, 98, 92, 23]. This recurses until the stack is empty (base case). On the way back up, each popped element is inserted via insertSorted:

• Insert 23 into [] — stack is empty, push 23. Stack: [23]
• Insert 92 into [23] — 92 > 23, push 92. Stack: [92, 23]
• Insert 98 into [92, 23] — 98 > 92, push 98. Stack: [98, 92, 23]
• Insert 31 into [98, 92, 23] — 31 < 98, pop 98. 31 < 92, pop 92. 31 > 23, push 31. Push 92 back. Push 98 back. Stack: [98, 92, 31, 23]
• Insert 3 into [98, 92, 31, 23] — 3 < 98, pop. 3 < 92, pop. 3 < 31, pop. 3 < 23, pop. Stack empty, push 3. Push 23, 31, 92, 98 back. Stack: [98, 92, 31, 23, 3]
• Insert 34 into [98, 92, 31, 23, 3] — 34 < 98, pop. 34 < 92, pop. 34 > 31, push 34. Push 92, 98 back. Stack: [98, 92, 34, 31, 23, 3]

Final sorted stack (top to bottom): [98, 92, 34, 31, 23, 3].

C++ Implementation

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

void insertSorted(stack<int>& s, int element) {
    if (s.empty() || element > s.top()) {
        s.push(element);
        return;
    }
    int top = s.top();
    s.pop();
    insertSorted(s, element);
    s.push(top);
}

void sortStack(stack<int>& s) {
    if (s.empty()) return;
    int top = s.top();
    s.pop();
    sortStack(s);
    insertSorted(s, top);
}

int main() {
    stack<int> s;
    s.push(23); s.push(92); s.push(98);
    s.push(31); s.push(3); s.push(34);

    sortStack(s);

    cout << "Sorted stack (top to bottom): ";
    while (!s.empty()) {
        cout << s.top() << " ";
        s.pop();
    }
    return 0;
}

Output: Sorted stack (top to bottom): 98 92 34 31 23 3

Python Implementation

def insert_sorted(stack, element):
    if not stack or element > stack[-1]:
        stack.append(element)
        return
    top = stack.pop()
    insert_sorted(stack, element)
    stack.append(top)

def sort_stack(stack):
    if not stack:
        return
    top = stack.pop()
    sort_stack(stack)
    insert_sorted(stack, top)

stack = [23, 92, 98, 31, 3, 34]
sort_stack(stack)
print("Sorted stack (top to bottom):", stack[::-1])

Output: Sorted stack (top to bottom): [98, 92, 34, 31, 23, 3]

Complexity Comparison

Aspect	Temporary Stack (Iterative)	Recursion
Time complexity	O(n²) worst case	O(n²) worst case
Space complexity	O(n) for the temp stack	O(n) for the call stack
Best case	O(n) if input is already sorted	O(n) if input is already sorted
In-place?	No (uses a second stack explicitly)	No (call stack is implicit auxiliary storage)
Interview clarity	Easier to trace step-by-step	More compact code, harder to trace

Both methods are O(n²) because in the worst case (reverse-sorted input), every insertion requires moving all previously sorted elements. For a stack of n elements, the total comparisons sum to 1 + 2 + 3 + ... + (n-1) = n(n-1)/2.

The space complexity analysis matters here: students sometimes claim the recursive version is “in-place” because no explicit data structure is allocated. It is not. The call stack holds up to n frames during sortStack and up to n frames during insertSorted at any given point. Peak auxiliary memory is O(n) in both approaches.

When to Use Which

• Whiteboard interviews: temp-stack is preferable. You can draw two columns and trace every push/pop visibly.
• Online coding rounds: recursion is faster to type and has fewer loop variables to manage.
• Follow-up questions: interviewers sometimes ask “can you do this without a second stack variable?” The recursive answer satisfies this, since the call stack is implicit.

Common Interview Variations

Interviewers rarely ask the base problem in isolation. Expect follow-ups:

• Sort in ascending order (smallest on top): flip the comparison. In the temp-stack method, change tempStack.top() > current to tempStack.top() < current. In the recursive method, change element > s.top() to element < s.top().
• Find the minimum element using a temp stack: a simpler version of the same shuttle logic. Pop elements to temp, track the minimum, push everything back.
• Insert an element at its sorted position in an already-sorted stack: this is literally the insertSorted helper. Recognising it as a building block is the pattern interviewers test.
• Sort using two temporary stacks: reduces worst-case comparisons by simulating merge sort with three stacks total. Rarely asked at fresher level, but worth knowing exists.

The equilibrium index problem uses a conceptually similar technique: processing elements while maintaining running state (prefix sums vs. sorted invariant). Practising both builds fluency with the “maintain an invariant while scanning” pattern that recurs across stack and array problems.

The recursive decomposition here (break the problem into “sort the rest, then insert one element correctly”) is the same structural pattern that powers recursive prompt chaining in LLM applications: solve a smaller version of the problem, then integrate one new piece. TinkerLLM at ₹299 lets you build exactly that kind of recursive pipeline hands-on, starting from the decomposition intuition you already have from problems like this one.