Sort a Stack
Sort a stack using only stack operations and recursion — no arrays, no loops over indices.
Open on GeeksforGeeks ↗Intuition
Pop everything (recursion holds the elements in call frames), then insert each element back in sorted position — again recursively: pop while the top is bigger, drop the element, push everything back.
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
Peel with recursion
sort(): pop top, sort the rest, then insert the popped element into the now-sorted stack.
Sorted insert, also recursive
insert(x): if stack empty or top ≤ x, push x. Otherwise pop, insert(x) deeper, re-push.
Cost
Each insert may touch the whole stack → O(n²) moves, O(n) recursion depth. It's an exercise in recursion, not efficiency.
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.