Sort a Stack | Recursion

geeksforgeeks.org

Problem Statement

Given a stack of integers, sort the stack such that:

Smallest element at the bottom

Largest element at the top

You are allowed to use only stack operations.

---

Brute Force Intuition

In an interview, you can explain it like this:

Pop every element into an array, sort the array, and push the elements back into the stack.

This works but uses an extra array, violating the spirit of the problem.

Complexity

• Time Complexity: O(N log N)
• Space Complexity: O(N)

Brute Force Code

class Solution {

    public void sortStack(Stack<Integer> st) {

        int[] arr = new int[st.size()];

        int i = 0;

        while (!st.isEmpty()) {
            arr[i++] = st.pop();
        }

        Arrays.sort(arr);

        for (int num : arr) {
            st.push(num);
        }
    }
}

---

Moving Towards the Optimal Approach

Instead of using an extra array, can we use recursion itself as the temporary storage?

Yes.

The idea is:

Pop one element

↓

Sort remaining stack

↓

Insert the popped element
at its correct position

---

Pattern Recognition

Whenever you see:

• Stack
• Only stack operations allowed
• No extra data structure

Think:

Recursion + Backtracking

---

Key Observation

Suppose the stack is:

3
1
4
2

Pop:

3

Now recursively sort:

1
4
2

After it becomes sorted:

1
2
4

Insert:

3

at its correct position.

---

Optimal Approach

Create two recursive functions:

sort()

Pop Top

↓

Sort Remaining Stack

↓

Insert Element Back

---

insert()

If:

Stack Empty

OR

Top <= Current

Push directly.

Otherwise:

Pop

↓

Insert Recursively

↓

Push Back

---

Optimal Java Solution

class Solution {

    public void sortStack(Stack<Integer> st) {

        if (st.isEmpty())
            return;

        int top = st.pop();

        sortStack(st);

        insert(st, top);
    }

    private void insert(Stack<Integer> st, int num) {

        if (st.isEmpty() || st.peek() <= num) {

            st.push(num);
            return;
        }

        int top = st.pop();

        insert(st, num);

        st.push(top);
    }
}

---

Dry Run

Input

Top

2
4
1
3

---

Step 1

Pop:

2

Recursively sort:

4
1
3

---

Step 2

Eventually stack becomes:

1
3
4

Now insert:

2

Pop:

4

Pop:

3

Insert:

2

Push back:

3

4

Final Stack:

Top

4
3
2
1

Largest element remains on top.

---

Why Recursion Works?

Recursion automatically stores removed elements on the function call stack.

After sorting the smaller stack:

Insert every removed element
back into its correct position.

This eliminates the need for an extra array.

---

Complexity Analysis

Metric	Complexity
Time Complexity	O(N²)
Space Complexity	O(N) (Recursion Stack)

---

Interview One-Liner

Recursively sort the smaller stack, then insert the removed element back into its correct position using another recursive function.

---

Pattern Learned

Stack
+
No Extra Data Structure
+
Maintain Order

=> Recursion

Similar Problems

• Sort a Stack
• Reverse a Stack
• Delete Middle Element of Stack
• Reverse Stack Using Recursion

---

Memory Trick

Think:

Pop Everything

↓

Sort Smaller Stack

↓

Insert Back

Mental Model

Sort Stack

↓

Remove Top

↓

Sort Remaining

↓

Insert at Correct Position

Whenever you hear:

"Sort a stack without using another data structure"

your brain should immediately think:

Recursion + Insert in Sorted Order