← Amazon questions

Sort a stack using recursion

Filed under Amazon

Free read 3 of 3

The 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

  1. If the stack is empty, return.

Solution

O(n^2) time, O(n) space

Python
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.