Sort a Stack Using Another Stack

Sorting a stack with only stack operations (push, pop, peek, isEmpty) is a classic interview question. You cannot use arrays, heaps, or any other data structure — just one additional stack.

The Algorithm

The idea mirrors insertion sort: maintain a sorted temporary stack, and for each element from the input stack, find its correct position in the temporary stack.

def sort_stack(stack):
    """
    Sort a stack so that the smallest element is on top.
    Time: O(n²), Space: O(n)
    """
    temp = []

    while stack:
        current = stack.pop()

        # Move elements from temp back to stack
        # until we find the right position for current
        while temp and temp[-1] > current:
            stack.append(temp.pop())

        temp.append(current)

    # Copy sorted elements back
    while temp:
        stack.append(temp.pop())

    return stack

Step-by-Step Trace

Input stack (top → bottom): [5, 1, 3, 2, 4]

Step | current | stack         | temp (sorted)
-----|---------|---------------|---------------
  1  |    4    | [5,1,3,2]    | [4]
  2  |    2    | [5,1,3]      | [4] → move 4 back → [2,4]
  3  |    3    | [5,1,4]      | [2] → [2,3] then 4 back → [2,3,4]
  4  |    1    | [5]          | [2,3,4] → move all back → [1,2,3,4]
  5  |    5    | []           | [1,2,3,4,5]

Final sorted stack (top → bottom): [1, 2, 3, 4, 5]

Why O(n²)?

In the worst case (reverse sorted input), every element requires moving all elements from temp back to the input stack. For n elements, this creates roughly n + (n-1) + … + 1 = n(n+1)/2 moves.

Recursive Approach

You can also sort a stack using recursion (the call stack acts as the temporary storage):

def sort_stack_recursive(stack):
    """
    Sort stack using recursion.
    Time: O(n²), Space: O(n) call stack
    """
    if not stack:
        return

    top = stack.pop()
    sort_stack_recursive(stack)
    _insert_sorted(stack, top)


def _insert_sorted(stack, value):
    if not stack or stack[-1] <= value:
        stack.append(value)
        return

    top = stack.pop()
    _insert_sorted(stack, value)
    stack.append(top)

Sorting in Descending Order

To sort so the largest element is on top, just flip the comparison:

def sort_stack_descending(stack):
    temp = []

    while stack:
        current = stack.pop()
        while temp and temp[-1] < current:  # Changed > to <
            stack.append(temp.pop())
        temp.append(current)

    while temp:
        stack.append(temp.pop())

    return stack

Edge Cases

• Empty stack — returns immediately
• Single element — already sorted
• All duplicates — works correctly, duplicates stay adjacent
• Already sorted — runs in O(n) since inner loop never executes

When to Use This Pattern

• Interview questions that restrict you to stack operations only
• When you need to maintain sorted order in a stack-based system
• As a building block for more complex stack problems

Related Problems

• Min Stack — maintain minimum in O(1) with an auxiliary stack
• Stack with getMax() — similar auxiliary stack technique
• Sort a linked list — merge sort is preferred (O(n log n))
• Implement a priority queue with stacks — uses this as a subroutine