DSA 450 Notes

Problem Statement

Sort a stack in ascending order (smallest at top, largest at bottom) using only recursion. You cannot use any loop constructs or additional data structures.

Example:

Input: Stack = [34, 3, 31, 98, 92, 23] (23 is top)
Output: Stack = [3, 23, 31, 34, 92, 98] (3 is top)

Input: Stack = [3, 2, 1] (1 is top)
Output: Stack = [1, 2, 3] (1 is top)

Approach: Using Two Recursive Functions

Intuition

Similar to reversing a stack, we use two recursive functions:

sortStack: Pop each element, sort remaining stack, insert popped element in sorted order
sortedInsert: Insert an element in its correct sorted position

Algorithm

Pop the top element
Recursively sort the remaining stack
Insert the popped element at its correct sorted position
Base case: stack with 0 or 1 element is already sorted

java

import java.util.*;

public class SortStack {
    // Helper function to insert element in sorted order
    public static void sortedInsert(Stack<Integer> stack, int x) {
        // Base case: stack is empty or top is smaller than x
        if (stack.isEmpty() || stack.peek() <= x) {
            stack.push(x);
            return;
        }
        
        // Pop the top element
        int top = stack.pop();
        
        // Recursively insert x in sorted order
        sortedInsert(stack, x);
        
        // Push top back
        stack.push(top);
    }
    
    // Main function to sort stack
    public static void sortStack(Stack<Integer> stack) {
        // Base case: empty stack
        if (stack.isEmpty()) {
            return;
        }
        
        // Pop the top element
        int top = stack.pop();
        
        // Sort the remaining stack
        sortStack(stack);
        
        // Insert the popped element in sorted order
        sortedInsert(stack, top);
    }
    
    public static void printStack(Stack<Integer> stack) {
        System.out.println("Stack (bottom to top): " + stack);
    }
    
    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();
        stack.push(34);
        stack.push(3);
        stack.push(31);
        stack.push(98);
        stack.push(92);
        stack.push(23);
        
        System.out.println("Before sorting:");
        printStack(stack);
        
        sortStack(stack);
        
        System.out.println("After sorting:");
        printStack(stack);
    }
}

Complexity Analysis

Time Complexity: O(n^2)
- sortStack is called n times
- Each sortedInsert can take O(n) time in worst case
- Total: O(n) * O(n) = O(n^2)
Space Complexity: O(n) - recursion stack depth

Detailed Trace

Let's trace through: Stack = [3, 2, 1] (1 is top), sorting to get smallest on top

sortStack([3, 2, 1]):
  pop 1, call sortStack([3, 2])
    sortStack([3, 2]):
      pop 2, call sortStack([3])
        sortStack([3]):
          pop 3, call sortStack([])
            sortStack([]): return (base case)
          sortedInsert([], 3) → [3]
        Stack is now [3]
      sortedInsert([3], 2):
        3 > 2, so pop 3
        sortedInsert([], 2) → [2]
        push 3 back → [2, 3]
    Stack is now [2, 3] (2 is top)
  sortedInsert([2, 3], 1):
    2 > 1, so pop 2
    sortedInsert([3], 1):
      3 > 1, so pop 3
      sortedInsert([], 1) → [1]
      push 3 back → [1, 3]
    push 2 back → [1, 2, 3]
Stack is now [1, 2, 3] (1 is top) ✓

Variation: Sort in Descending Order (Largest on Top)

Just change the comparison in sortedInsert:

Key Takeaways

Two recursive functions work together:
- sortStack: extracts elements one by one
- sortedInsert: places each element in correct position
Similar to insertion sort - each element is inserted in its correct position
Time complexity is O(n^2) - similar to insertion sort
The recursion stack acts as implicit storage
This demonstrates that recursion can replace loops entirely
The key insight: a sorted stack + one element can be re-sorted by finding the right position

Sort a Stack using recursion