☕ DSA Java Articles

Topics › Recursion and Backtracking › Get a Strong Hold

Sort a stack using recursion

Medium TUF ID 2858 A2Z

Java source ↗ Edit this article ↗

Problem

You are given a stack of integers. Sort it so that the largest element is on top and the smallest at the bottom, using only the stack operations push, pop, peek and isEmpty, and recursion. No loops, no arrays, no second stack: the only extra storage allowed is the function call stack itself.

Constraints: up to a few thousand elements; values fit in an int.

In Java the stack is a Deque<Integer> backed by ArrayDeque, whose push, pop and peek all act on the top. The legacy java.util.Stack class would work the same way but is not recommended for new code. Examples below list the stack from bottom to top, so the last value written is the one on top.

Example 1

stack (bottom to top) = [3, 1, 2]
answer                = [1, 2, 3]     // 3 is on top

Example 2

stack (bottom to top) = [11, 2, 32, 3, 41]
answer                = [2, 3, 11, 32, 41]

Two methods in the Java file break the “stack operations only” rule on purpose: they are the baselines the recursive solution is checked against.

Approach 1: Brute force, copy out and sort

Intuition. Treat the stack as a bag of numbers. Pop everything into a list, sort the list, and push the values back from smallest to largest so that the largest ends on top.

Algorithm.

  1. Pop every element into an ArrayList.
  2. Sort the list in ascending order.
  3. Push the elements back in that order.
static void sortViaList(Deque<Integer> stack) {
    List<Integer> items = new ArrayList<>();
    while (!stack.isEmpty()) items.add(stack.pop());
    Collections.sort(items);                           // ascending
    for (int v : items) stack.push(v);                 // smallest pushed first, so the largest ends on top
}

Complexity. Time O(n log n) for the sort. Space O(n) for the list.

This is the fastest way to sort a stack and what you would write in production. The exercise forbids it because its purpose is to practise recursion.

Approach 2: Insertion sort with a helper stack

Intuition. Insertion sort maintains a sorted prefix and inserts one new element at a time. With stacks, the “sorted prefix” is a second stack helper whose smallest element is on top. To insert v, first move every element of helper that is smaller than v back onto the input stack (they will be re-inserted later), push v, and continue. When the input is empty, pour helper back: its smallest element comes out first and is pushed first, so the largest finishes on top.

Algorithm.

  1. While the input stack is not empty, pop v.
  2. While helper is not empty and helper.peek() < v, pop from helper and push onto the input.
  3. Push v onto helper.
  4. When the input is empty, pop everything from helper and push it onto the input.
static void sortWithHelperStack(Deque<Integer> stack) {
    Deque<Integer> helper = new ArrayDeque<>();        // invariant: sorted, smallest on top
    while (!stack.isEmpty()) {
        int v = stack.pop();
        while (!helper.isEmpty() && helper.peek() < v) stack.push(helper.pop());   // smaller ones wait on the input
        helper.push(v);
    }
    while (!helper.isEmpty()) stack.push(helper.pop()); // pour back: smallest first, largest on top
}

Dry run on [3, 1, 2] (bottom to top), writing stacks bottom to top:

step input helper note
pop 2 [3, 1] [2] helper empty, push
pop 1 [3] [2, 1] 2 is not smaller than 1
pop 3 [1, 2] [3] 1 and 2 are smaller than 3, moved back
pop 2 [1] [3, 2]  
pop 1 [] [3, 2, 1]  
pour back [1, 2, 3] [] 1 pushed first, 3 last

Complexity. Time O(n^2) in the worst case, because an element can be moved back and forth many times. Space O(n) for the helper stack.

This approach is the bridge to the recursive one: the recursion below does exactly the same work, but the helper stack is replaced by the call stack.

Approach 3: Optimal, recursion only

Intuition. Recursion gives us a place to park one element per call: the local variable of a stack frame. “Sort this stack” becomes: pop the top, trust the recursion to sort the remaining n - 1 elements, then put the popped value back in its correct place. That second step is itself recursive: “insert v into a sorted stack” means pop elements larger than v one at a time (each parked in its own frame), push v when the top is no longer larger, then push the parked elements back on the way up.

Algorithm.

sortRecursive(stack):

  1. If the stack is empty, return.
  2. top = pop().
  3. sortRecursive(stack).
  4. insertSorted(stack, top).

insertSorted(stack, v):

  1. If the stack is empty or peek() <= v, push v and return.
  2. top = pop().
  3. insertSorted(stack, v).
  4. push(top).
static void sortRecursive(Deque<Integer> stack) {
    if (stack.isEmpty()) return;                       // base case: nothing to sort
    int top = stack.pop();
    sortRecursive(stack);                              // the remaining n - 1 elements, sorted
    insertSorted(stack, top);
}

static void insertSorted(Deque<Integer> stack, int v) {
    if (stack.isEmpty() || stack.peek() <= v) {        // base case: v belongs on top
        stack.push(v);
        return;
    }
    int top = stack.pop();                             // top > v: lift it off
    insertSorted(stack, v);                            // place v below it
    stack.push(top);                                   // and put the larger one back
}

Dry run on [3, 1, 2] (bottom to top). Each sortRecursive frame pops one value, then the frames unwind from the smallest problem:

frame holds stack before insert after insertSorted
sort #3 (deepest) 3 [] [3]
sort #2 1 [3] pop 3 (3 > 1), push 1, push 3 → [1, 3]
sort #1 2 [1, 3] pop 3 (3 > 2), top is 1 ≤ 2 so push 2, push 3 → [1, 2, 3]

The order in which frames finish is the reverse of the order they started, so the element popped last (the original bottom, 3) is inserted first into an empty stack, and the original top (2) is inserted last.

Complexity. Time O(n^2): n insertions, each popping up to n elements. Space O(n) for the recursion, up to n frames of sortRecursive plus up to n frames of insertSorted at the deepest point.

“Optimal” here means optimal under the problem’s constraint, not the fastest possible: Approach 1 is faster, but it uses an auxiliary data structure. The recursive version uses nothing but the call stack, which is the skill the problem is teaching.

Edge cases and pitfalls