Sort Stack

Tags

Sort Stack

Category

Stacks

Difficulty

Medium

Problem Statement

Given a stack of integers, sort it in ascending order (smallest on top) using only stack operations: push, pop, peek, and isEmpty. You may use one additional temporary stack but no other data structures.

Intuition

Since we can only access the top of a stack, sorting requires repeatedly finding the correct position for each element. By using a recursive approach, we can pop all elements off the stack (via the call stack), then insert each element back in sorted order. The insertion step places each element below all elements that are smaller than it, maintaining sorted order from top to bottom.

Approach

  1. Recursive sort: If the stack is not empty, pop the top element, recursively sort the remaining stack, then insert the popped element back in its correct sorted position.
  2. Insert in sorted order: To insert a value into an already-sorted stack:
    • If the stack is empty or the top element is less than or equal to the value, push the value.
    • Otherwise, pop the top element, recursively insert the value, then push the popped element back on top.

Pseudocode

function sortStack(stack):
    if stack is empty:
        return stack

    top = stack.pop()
    sortStack(stack)
    insertInSortedOrder(stack, top)
    return stack

function insertInSortedOrder(stack, value):
    if stack is empty or stack.peek() <= value:
        stack.push(value)
    else:
        top = stack.pop()
        insertInSortedOrder(stack, value)
        stack.push(top)

Time & Space Complexity

  • Time: O(n^2) where n is the number of elements in the stack. Each insertion into the sorted portion can take up to O(n) pops and pushes.
  • Space: O(n) for the recursion call stack. The recursive sort goes n levels deep, and each insertion can add up to n more frames.

Key Insights

  • The recursion effectively uses the call stack as temporary storage, adhering to the constraint of not using other data structures.
  • The algorithm is analogous to insertion sort: each element is placed into its correct position within an already-sorted sequence.
  • The sorted order is smallest on top. Adjusting the comparison in insertInSortedOrder changes the sort direction.
  • An iterative solution using an explicit temporary stack is also possible and follows a similar insertion-based logic.

Edge Cases

  • Empty stack: already sorted, return as-is.
  • Stack with one element: already sorted.
  • Stack already sorted: each insertion finds its position immediately, but worst-case comparisons still occur.
  • Stack sorted in reverse order: each insertion requires moving all previously sorted elements, leading to the worst-case O(n^2) time.
  • Stack with duplicate values: handled correctly since the comparison uses <=.
  • Stack with all identical elements: each insertion is O(1), so total time is O(n).

Linked mentions