Sort a stack using recursion
Filed under Amazon
Free read 3 of 3The question
Sort a stack in ascending order using only recursion. You cannot use any additional data structures like arrays or other stacks.
Constraints
- No iterative loops allowed
- No extra data structures
- Stack size N
Examples
- Input
- [3, 1, 4, 2]
- Output
- [1, 2, 3, 4]
- Why
- The stack is sorted such that the smallest element is at the top.
Approach
If the stack is empty, return.
Pop the top element and recursively sort the remaining stack.
Create a helper function to insert the popped element back into the sorted stack at the correct position.
Solution
O(n^2) time, O(n) space
def sort_stack(s):
if s:
temp = s.pop()
sort_stack(s)
insert(s, temp)
def insert(s, val):
if not s or s[-1] < val:
s.append(val)
else:
temp = s.pop()
insert(s, val)
s.append(temp)
Tips
- What they are testing: Tests recursion depth and stack frame management.
- Common mistake: Using an auxiliary stack or global variable to store elements.
Related Amazon questions
Collected from public candidate posts and coding forums. Updated Nov 2026.