Sort a Stack
Sort a stack using only stack operations and recursion — no arrays, no loops over indices.
Open on GeeksforGeeks ↗02
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.
03
Approach
1
Peel with recursion
sort(): pop top, sort the rest, then insert the popped element into the now-sorted stack.
2
Sorted insert, also recursive
insert(x): if stack empty or top ≤ x, push x. Otherwise pop, insert(x) deeper, re-push.
3
Cost
Each insert may touch the whole stack → O(n²) moves, O(n) recursion depth. It's an exercise in recursion, not efficiency.
04
Solution & live demo
python
▶1def sorted_insert(stack, x):
▶2 if not stack or stack[-1] <= x:
▶3 stack.append(x)
▶4 return
▶5 top = stack.pop()
▶6 sorted_insert(stack, x)
▶7 stack.append(top)
▶8
▶9def sort_stack(stack):
▶10 if stack:
▶11 top = stack.pop()
▶12 sort_stack(stack)
▶13 sorted_insert(stack, top)
▶14 return stack
05
Edge cases
Already sorted stack
Every insert hits the top ≤ x case immediately — O(n) total.
Duplicates
≤ comparison keeps them adjacent, insertion stable.
06
Complexity
Time
O(n²)
Space
O(n)
Call stack replaces the auxiliary array.