Sort a Stack using recursion

The problem, simply

You get a stack of numbers. Sort it so the smallest number is at the bottom and the biggest is on top. You may only use stack moves (push, pop, peek, isEmpty) and recursion. No loops over other arrays, no second stack, no list.

Some versions ask for the smallest on top instead. The method is the same; you only flip one comparison.

A story to remember it

Picture it

Examples

Way 1: the simple way

If you were allowed a list, you would pour the stack into it, sort the list, and pour it back.

1. Pop everything into a list.
2. Sort the list from small to big.
3. Push the list from the smallest to the biggest. The biggest is pushed last, so it ends on top.

import java.util.*;

class Solution {
    public void sort(Deque<Integer> stack) {
        List<Integer> all = new ArrayList<>();
        while (!stack.isEmpty()) all.add(stack.pop());
        Collections.sort(all);                         // small to big
        for (int x : all) stack.push(x);               // the biggest is pushed last, so it is on top
    }
}

How long it takes: sorting is O(n log n). Extra room: the list, O(n). It is faster, but it breaks the rule about other structures.

Way 2: the clever way

Two recursive functions, just like reversing a stack.

sortedInsert(x) puts x into an already sorted stack:

1. If the stack is empty, or the top is not bigger than x, push x. Done.
2. Otherwise pop the top and hold it, call sortedInsert(x) again, then push the held number back.

sort() sorts the whole stack:

1. If the stack is empty, stop.
2. Pop the top and hold it, call sort() on the rest, then sortedInsert(held).

import java.util.*;

class Solution {
    public void sort(Deque<Integer> stack) {
        if (stack.isEmpty()) return;
        int top = stack.pop();            // hold one number
        sort(stack);                      // sort the rest
        sortedInsert(stack, top);         // drop the held number into its place
    }

    private void sortedInsert(Deque<Integer> stack, int x) {
        if (stack.isEmpty() || stack.peek() <= x) {
            stack.push(x);                // the top is not bigger: x belongs here
            return;
        }
        int held = stack.pop();           // a bigger number is in the way, lift it
        sortedInsert(stack, x);
        stack.push(held);                 // put it back on top
    }
}

How long it takes: there are n inserts and each one may lift every number already sorted, so the total is up to 0 + 1 + ... + (n - 1), which is O(n^2). This is insertion sort, done with the call stack. Extra room: at most about n waiting calls, O(n).

For smallest on top, change stack.peek() <= x to stack.peek() >= x.

Another way: one helper stack, no recursion

A common follow up: sort with one extra stack and loops. Keep the helper sorted with the smallest on top. Pop a number x from the input. While the helper's top is smaller than x, move those numbers back to the input. Then push x onto the helper. At the end, pour the helper back: the smallest goes in first, so the biggest ends on top.

import java.util.*;

class Solution {
    public void sort(Deque<Integer> stack) {
        Deque<Integer> helper = new ArrayDeque<>();      // kept with the smallest on top
        while (!stack.isEmpty()) {
            int x = stack.pop();
            while (!helper.isEmpty() && helper.peek() < x) {
                stack.push(helper.pop());                // smaller ones step back into the input
            }
            helper.push(x);
        }
        while (!helper.isEmpty()) stack.push(helper.pop());  // smallest in first, biggest ends on top
    }
}

Numbers that step back into the input get popped again later, so this is also O(n^2) time in the worst case, with O(n) room for the helper.

Watch out for

• Using < instead of <= in sortedInsert. It still sorts, but equal numbers get lifted for no reason.
• Forgetting the empty check before peek(). ArrayDeque.peek() returns null on an empty stack, and comparing null with an int throws.
• Deep recursion. A stack of 100,000 numbers means 100,000 waiting calls and a likely StackOverflowError.

What interviewers ask next

• Why is it O(n^2) and not O(n)? Each insert can lift all the numbers already sorted, like insertion sort on a reversed list.
• Reverse a stack with recursion. Same shape, but insert at the bottom instead of in sorted order.
• Sort a stack with no recursion and only one extra stack. That is the "Another way" above.
• Can a stack be sorted faster? Any sort that only compares pairs needs O(n log n) comparisons. With two helper stacks you can do a merge sort in O(n log n); with only the call stack or one helper, the simple methods above are O(n^2).

Remember this

Grown-up words: the tower is a stack, the helpers are frames on the call stack, sortedInsert is the insert step of insertion sort, and "no other structure" means no auxiliary data structure.