Sort a Stack
Sort a stack using only stack operations and recursion — no arrays, no loops over indices.
- 1 <= n <= 10³
- -10⁹ <= value <= 10⁹
- Only stack operations and recursion are permitted
Intuition
To sort a stack using only stack operations and recursion, you give up everything that normally makes sorting easy. No indexing, no swapping two arbitrary elements, no scanning. The only things available are push, pop, peek, and the call stack.
The key realisation is that recursion gives you a second place to store data. When you pop an element and recurse, that element is held safely in a call frame while the deeper call works on a smaller stack. Unwinding gives the elements back in reverse order, one per frame.
That suggests an insertion sort turned inside out. To sort a stack: pop the top, sort what remains, then put the popped element back in its correct position rather than on top.
That last step needs its own recursion, since you cannot reach into the middle of a stack:
- To insert x into a sorted stack, pop everything larger than x, push x, then push the popped elements back.
Again the call frames do the holding. Two mutually supporting recursions — one to peel the stack down, one to insert an element into a sorted stack — and neither ever uses an auxiliary array. This is an exercise in thinking recursively, not an efficient sort; the cost is O(n²) and that is inherent to the constraints.
The constraint is the puzzle: no arrays, no extra containers — only stack operations. When the only storage you're allowed is the call stack, recursion becomes the data structure. The shape is always the same: pop one item, solve the smaller problem, then re-insert the held item correctly on the way back up. Reversing a stack works identically.
Approach
Before reading on: price up what plain recursion costs here, then ask what unresolved thing you are holding, and what event finally resolves it. Aim for O(n²) time and O(n) space.
Peel the stack down with recursion
In sort(), if the stack is empty, return. Otherwise pop the top element, call sort() on the smaller stack, then insert the popped element back into it. The popped value lives in the call frame while the recursion works below it — that frame is the only storage you are allowed.
Insert into an already-sorted stack
After the recursive sort() returns, everything below is in order and the held element must go into its correct place. That job belongs to a second function, insert(x), because reaching into the middle of a stack is impossible with push and pop alone.
Base case of the insert
If the stack is empty, or its top is less than or equal to x, then x belongs right here — push it and return. This is the moment the element lands in its sorted position, and every deeper frame is now free to unwind.
Otherwise pop, recurse, and push back
If the top is greater than x, it must end up above x. Pop it, call insert(x) on the smaller stack, then push the popped element back on the way out. The push after the recursive call is what restores the elements — omitting it silently discards data.
Cost of the two recursions
Each insert may touch every element, and it runs once per element, giving O(n²) time. Recursion depth reaches O(n) for both functions, so stack space is O(n). No practical sort works this way — the point is the technique, and interviewers ask it to see whether you can use the call stack as storage.
Solution & live demo
Common pitfalls
Pushing the held element back before recursing
top = stack.pop() stack.append(top) sort_stack(stack)
top = stack.pop() sort_stack(stack) sorted_insert(stack, top)
Putting it straight back leaves the stack exactly as it was, so the recursion never shrinks the problem and never terminates. The held element has to stay out — in the call frame — while the rest is sorted, and only then be inserted into its correct place.
Appending in sorted_insert without unwinding first
def sorted_insert(stack, x):
stack.append(x)if not stack or stack[-1] <= x:
stack.append(x)
return
top = stack.pop()
sorted_insert(stack, x)
stack.append(top)A stack only exposes its top, so an element that belongs deeper can't be placed directly. You lift off everything larger, drop the value in, then push the lifted items back — that unwinding is the insertion.
Using < and infinitely recursing on duplicates
if not stack or stack[-1] < x:
if not stack or stack[-1] <= x:
With two equal values neither can settle above the other: the guard keeps failing, the value is lifted and reinserted forever. Allowing equality lets a duplicate rest on its twin and the recursion bottoms out.
Edge cases
Every insert hits the top ≤ x case immediately — O(n) total.
≤ comparison keeps them adjacent, insertion stable.