AlgoViz
HomeRecursion

Sort a stack using recursion

Medium

Pop everything, insert on the way back

Problem

Sort a stack in ascending order using only recursion (no extra data structures).

In simple words

Pop everything off, then insert each back in its sorted place recursively.

The idea

Pop the top, sort the rest recursively, then insert the popped value into its sorted position with a second recursive helper. The call stack is doing the job of the auxiliary structure you are not allowed to use.

The trick

  • Two recursions: one to empty the stack, one to insert in order.
  • Insert pops until the top is smaller, pushes the value, then pushes back.
  • O(n²) time, O(n) stack.

This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.

3
1
2
0
1
2

Step 1 of 2. Here's the example — bottom [3,1,2] top Values: 3, 1, 2.

1/2
Optimal
timeO(n^2)spaceO(n)
1sort(st):2  if empty: return3  x = pop()4  sort(st)5  insertSorted(st, x)

Input

array
[3, 1, 2]

Output

answer
—

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Example

Input:
bottom [3,1,2] top
Output:
bottom [1,2,3] top

Practice this problem:GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.