Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Sort a Stack Recursively

MEDIUMProblemSolveExternal Links

Description

You are given a stack of integers. Your task is to sort the stack in ascending order so that the smallest element is at the bottom and the largest element is at the top.

You should accomplish this using recursion — without using any loop constructs for the core sorting logic. The only operations allowed on the stack are:

  • push(x) — place element x on top of the stack
  • pop() — remove and return the top element
  • top() / peek() — view the top element without removing it
  • isEmpty() — check whether the stack is empty

The stack is represented as a list where the first element is at the bottom and the last element is at the top. For example, [5, 1, 3] means 5 is at the bottom and 3 is at the top.

Examples

Example 1

Input: stack = [5, 1, 3] (bottom=5, top=3)

Output: [1, 3, 5] (bottom=1, top=5)

Explanation: The original stack has 5 at the bottom and 3 at the top. After sorting, 1 (the smallest) is at the bottom and 5 (the largest) is at the top. The stack now reads 1, 3, 5 from bottom to top — sorted in ascending order.

Example 2

Input: stack = [11, 2, 32, 3, 41] (bottom=11, top=41)

Output: [2, 3, 11, 32, 41] (bottom=2, top=41)

Explanation: The elements 11, 2, 32, 3, 41 are rearranged so that each element is less than or equal to the one above it: 2 ≤ 3 ≤ 11 ≤ 32 ≤ 41.

Example 3

Input: stack = [1, 2, 3] (bottom=1, top=3)

Output: [1, 2, 3]

Explanation: The stack is already sorted in ascending order, so no changes are needed.

Constraints

  • 1 ≤ stack size ≤ 10^3
  • 0 ≤ stack elements ≤ 10^3

Editorial

Brute Force

Intuition

The simplest way to sort a stack is to transfer all its elements to a more flexible data structure, sort that structure, and transfer the elements back.

Think of it like having a tall tube of numbered balls (the stack). You can only take balls from the top. The easiest solution? Dump all the balls into a bowl (an array), arrange them in order, and drop them back into the tube one by one — smallest first so it sits at the bottom, then the next smallest, and so on until the largest lands on top.

This works because arrays support random access and have efficient built-in sorting algorithms. We trade the stack's restrictive access pattern for the array's flexibility.

Step-by-Step Explanation

Let's trace through with stack = [5, 1, 3] (bottom=5, top=3):

Step 1: Pop the top element 3. Stack becomes [5, 1]. Store 3 in an array.

Step 2: Pop 1 from the stack. Stack: [5]. Array: [3, 1].

Step 3: Pop 5 from the stack. Stack is now empty: []. Array: [3, 1, 5].

Step 4: Sort the array: [3, 1, 5] → [1, 3, 5].

Step 5: Push elements from the sorted array back to the stack. Push 1 first so it sits at the bottom. Stack: [1].

Step 6: Push 3. Stack: [1, 3].

Step 7: Push 5 (largest) last so it sits on top. Stack: [1, 3, 5].

Result: Stack is sorted — bottom to top: 1, 3, 5.

Brute Force: Pop All → Sort Array → Push Back — Watch how we pop every element into an array, sort it, and push elements back in ascending order so the smallest ends up at the bottom.

Algorithm

  1. Create an empty array (or list)
  2. While the stack is not empty:
    • Pop the top element and append it to the array
  3. Sort the array in ascending order
  4. For each element in the sorted array (from smallest to largest):
    • Push it onto the stack
  5. The stack is now sorted with smallest at bottom and largest at top

Code

#include <stack>
#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    void sortStack(stack<int> &s) {
        vector<int> arr;
        while (!s.empty()) {
            arr.push_back(s.top());
            s.pop();
        }
        sort(arr.begin(), arr.end());
        for (int val : arr) {
            s.push(val);
        }
    }
};
class Solution:
    def sortStack(self, s):
        arr = []
        while s:
            arr.append(s.pop())
        arr.sort()
        for val in arr:
            s.append(val)
import java.util.*;

class Solution {
    public void sortStack(Stack<Integer> s) {
        List<Integer> arr = new ArrayList<>();
        while (!s.isEmpty()) {
            arr.add(s.pop());
        }
        Collections.sort(arr);
        for (int val : arr) {
            s.push(val);
        }
    }
}

Complexity Analysis

Time Complexity: O(n log n)

Popping all n elements is O(n). Sorting the array uses a comparison-based sort, which runs in O(n log n). Pushing n elements back is O(n). The dominant term is O(n log n).

Space Complexity: O(n)

We use an auxiliary array of size n to store all the stack elements during sorting.

Why This Approach Is Not Efficient

While the array-based approach achieves the best possible time complexity of O(n log n), it completely bypasses the stack abstraction. By transferring elements to an array, we gain random access — but that converts the problem into ordinary array sorting, which any standard library can do.

The real purpose of this problem is to develop skill in recursive problem decomposition and stack-specific manipulation. In an interview, transferring to an array would show that you can sort, but not that you understand how to work within the constraints of a stack.

Moreover, this approach uses O(n) extra space for the auxiliary array on top of the stack. The recursive approach, while having O(n²) time complexity, teaches a powerful pattern: removing the top element, recursively solving the smaller problem, and inserting the element back in its correct position. This pattern appears in many other recursion and stack problems.

Optimal Approach - Recursive Sort

Intuition

The recursive approach breaks the problem into two elegant pieces:

Piece 1 — sortStack: To sort an entire stack, remove the top element, recursively sort the remaining (now smaller) stack, then insert the removed element back into its correct position in the now-sorted stack.

Piece 2 — sortedInsert: To insert an element into an already-sorted stack at the correct position: if the stack is empty or the top element is smaller than or equal to the element we are inserting, simply push it. Otherwise, pop the top, recursively insert our element into the remaining stack, then push the popped element back on top.

Think of it like organizing a deck of cards using only one hand. You pick up the top card, ask a helper to sort the remaining cards (recursion!), and then slide the card you are holding back into the correct spot in the now-sorted deck.

The beauty of this approach is that the call stack itself acts as temporary storage. When we pop elements in sortedInsert to make room, those elements are held in recursive stack frames and automatically pushed back in the correct order as the recursion unwinds.

Diagram showing the recursive sort concept: remove top element, sort remaining stack recursively, then insert element at correct position
Diagram showing the recursive sort concept: remove top element, sort remaining stack recursively, then insert element at correct position

Step-by-Step Explanation

Let's trace through with stack = [5, 1, 3] (bottom=5, top=3):

Step 1: Call sortStack. Pop top element 3 and hold it in the recursion. Stack: [5, 1]. Recursively sort the remaining stack.

Step 2: Call sortStack on [5, 1]. Pop 1 and hold it. Stack: [5]. Recurse again.

Step 3: Call sortStack on [5]. Pop 5 and hold it. Stack: []. Recurse on the empty stack.

Step 4: Base case — stack is empty. Now begin inserting held elements back in sorted order. Call sortedInsert([], 5). Stack is empty, so simply push 5. Stack: [5].

Step 5: Return to the frame holding 1. Call sortedInsert([5], 1). Top is 5, which is greater than 1. Pop 5 temporarily. Stack: [].

Step 6: Call sortedInsert([], 1). Stack is empty, push 1. Stack: [1].

Step 7: Push 5 back on top (the recursion unwinds). Stack: [1, 5]. Now 1 is correctly below 5.

Step 8: Return to the frame holding 3. Call sortedInsert([1, 5], 3). Top is 5, which is greater than 3. Pop 5 temporarily. Stack: [1].

Step 9: Call sortedInsert([1], 3). Top is 1, which is ≤ 3. Push 3 in this position. Stack: [1, 3].

Step 10: Push 5 back on top (recursion unwinds). Stack: [1, 3, 5].

Result: Stack is fully sorted: [1, 3, 5]. Each element was removed, the smaller stack was sorted recursively, and the element was inserted at exactly the right position.

Recursive Sort: sortStack + sortedInsert in Action — Watch how sortStack removes elements one by one, recurses to sort the remainder, and then sortedInsert places each element back at its correct sorted position.

Algorithm

Function sortStack(stack):

  1. If the stack is empty, return (base case)
  2. Pop the top element and store it as temp
  3. Recursively call sortStack(stack) to sort the remaining elements
  4. Call sortedInsert(stack, temp) to place temp at its correct position in the now-sorted stack

Function sortedInsert(stack, element):

  1. If the stack is empty OR the top element ≤ element:
    • Push element onto the stack (correct position found)
    • Return
  2. Otherwise:
    • Pop the top element and store it as top
    • Recursively call sortedInsert(stack, element)
    • Push top back onto the stack

The key insight is that sortedInsert uses the recursion stack as temporary storage: it pops elements that are too large, recurses to find the right spot, and the popped elements are automatically restored as the recursion unwinds.

Code

#include <stack>
using namespace std;

class Solution {
public:
    void sortedInsert(stack<int> &s, int element) {
        if (s.empty() || s.top() <= element) {
            s.push(element);
            return;
        }
        int top = s.top();
        s.pop();
        sortedInsert(s, element);
        s.push(top);
    }

    void sortStack(stack<int> &s) {
        if (s.empty()) return;
        int top = s.top();
        s.pop();
        sortStack(s);
        sortedInsert(s, top);
    }
};
class Solution:
    def sortedInsert(self, s, element):
        if not s or s[-1] <= element:
            s.append(element)
            return
        top = s.pop()
        self.sortedInsert(s, element)
        s.append(top)

    def sortStack(self, s):
        if not s:
            return
        top = s.pop()
        self.sortStack(s)
        self.sortedInsert(s, top)
import java.util.Stack;

class Solution {
    public void sortedInsert(Stack<Integer> s, int element) {
        if (s.isEmpty() || s.peek() <= element) {
            s.push(element);
            return;
        }
        int top = s.pop();
        sortedInsert(s, element);
        s.push(top);
    }

    public void sortStack(Stack<Integer> s) {
        if (s.isEmpty()) return;
        int top = s.pop();
        sortStack(s);
        sortedInsert(s, top);
    }
}

Complexity Analysis

Time Complexity: O(n²)

sortStack makes n recursive calls (one per element). Each call invokes sortedInsert, which in the worst case pops all elements of the already-sorted portion to find the correct position. For the k-th element, sortedInsert may perform up to k operations. The total work is 1 + 2 + 3 + ... + n = n(n+1)/2, which simplifies to O(n²).

The worst case occurs when the stack is initially sorted in descending order (largest at bottom), because every element must be inserted at the very bottom of the sorted stack.

Space Complexity: O(n)

The recursion uses the call stack as implicit storage. sortStack recurses to depth n (one frame per element), and within each frame, sortedInsert may recurse up to n levels deep. However, these are sequential (not nested simultaneously), so the maximum call stack depth at any point is O(n).

No explicit auxiliary data structures (arrays, extra stacks) are used — the call stack itself serves as temporary storage.