Category: Data structure

Sorting a Stack Using Recursion : In this tutorial, we will learn how to sort a stack of numbers using recursion in C++. A stack is a special data structure where you can only add or remove elements from the top, just like a stack of plates. Sorting a stack might seem tricky because you cannot access elements in the middle directly.

We will use recursion — a technique where a function calls itself — to break down the problem into smaller parts. First, we remove elements from the stack one by one until it’s empty. Then, we insert each removed element back into the stack in the correct sorted position.

This method does not use any extra data structures, and it helps you understand both recursion and stack operations deeply. The final result is a stack sorted in ascending order, with the smallest element at the bottom and the largest at the top.

The article also includes a step-by-step dry run to help beginners understand exactly how the stack changes during sorting.

What is a Stack?

A stack is a data structure that works like a pile of plates. You can only add or remove the top plate. This is called LIFO (Last In, First Out).

• You push to add an item on the top.
• You pop to remove the item from the top.
• You can check the top element anytime.

What Does Sorting a Stack Using Recursion program Do?

The program sorts the elements in a stack so that the smallest number is at the bottom and the largest number is at the top — all using recursion (functions calling themselves).

Code Breakdown of Sorting a Stack Using Recursion

#include <iostream>
#include <stack>
using namespace std;

• We include necessary libraries.
• stack helps us use stack data structure.
• iostream allows input/output.

Two Important Functions

1. sortedInsert — Inserts a number into the correct position in an already sorted stack.
2. sortStack — Sorts the entire stack using recursion.

Function: sortedInsert

void sortedInsert(stack<int> &st, int x) {
    if (st.empty() || st.top() > x) {
        st.push(x);
        return;
    }
    int temp = st.top();
    st.pop();
    sortedInsert(st, x);
    st.push(temp);
}

What it does:
It inserts x into the stack st in sorted order.

How?

• If stack is empty OR the top element is greater than x, push x directly (because it’s in the right position).
• Otherwise, remove the top element temporarily, call sortedInsert recursively to insert x in the smaller stack.
• After that, put back the temporarily removed element on top.

Function: sortStack of Sorting a Stack Using Recursion

void sortStack(stack<int> &st) {
    if (st.empty()) return;

    int x = st.top();
    st.pop();

    sortStack(st);

    sortedInsert(st, x);
}

What it does:
Sorts the stack by removing elements one by one and inserting them back in the sorted order.

How?

• Remove the top element x.
• Recursively sort the smaller stack.
• Insert the removed element x back into the sorted stack using sortedInsert.

main Function — Driver Code of Sorting a Stack Using Recursion

int main() {
    stack<int> st;

    st.push(30);
    st.push(10);
    st.push(50);
    st.push(20);
    st.push(40);

    // Print original stack
    cout << "Original Stack (top to bottom): ";
    stack<int> temp = st;
    while (!temp.empty()) {
        cout << temp.top() << " ";
        temp.pop();
    }
    cout << endl;

    // Sort the stack
    sortStack(st);

    // Print sorted stack
    cout << "Sorted Stack (top to bottom): ";
    while (!st.empty()) {
        cout << st.top() << " ";
        st.pop();
    }
    cout << endl;

    return 0;
}

Dry Run (Step by Step) | Sorting a Stack Using Recursion

Let’s dry run with the stack having elements (top to bottom):

40 (top), 20, 50, 10, 30 (bottom)

Step 1: sortStack is called with full stack

• Pop 40
• Recursively call sortStack with stack: 20, 50, 10, 30

Step 2: sortStack called again

• Pop 20
• Recursively call sortStack with stack: 50, 10, 30

Step 3: Next recursive call

• Pop 50
• Recursively call sortStack with stack: 10, 30

Step 4:

• Pop 10
• Recursively call sortStack with stack: 30

Step 5:

• Pop 30
• Recursively call sortStack with empty stack

Step 6:

• Stack is empty, return from recursion

Step 7: Now insert back the elements in sorted order using sortedInsert

• Insert 30 into empty stack → stack: 30

Step 8: Insert 10 into stack 30

• Compare top 30 > 10 → push 10 on top → stack: 10, 30

Step 9: Insert 50 into stack 10, 30

• 30 < 50, pop 30
• 10 < 50, pop 10
• Stack empty → push 50
• Push back popped 10 → stack: 10, 50
• Push back popped 30 → stack: 30, 10, 50
  Oops! This looks reversed — wait, order is important. Let’s check carefully:

Actually, the function pushes back in this order:

• After popping 30, then 10, stack empty
• push 50 → stack: 50
• push 10 → stack: 10, 50 (top is 10, then 50)
• push 30 → stack: 30, 10, 50 (top is 30)

But this is wrong, we want the smallest on the bottom.

Actually, when printing, top is on the left.

Wait, the way we visualize is top at left (in code top is accessed by st.top()), so the stack is:

• Top: 30
• then: 10
• then: 50

So 30 is on top, 10 below it, 50 at bottom → not sorted.

So something is wrong in our understanding.

But the code is correct. The explanation is: the stack stores elements with the top being the last pushed.

Let’s clarify: In the code, the stack top is the last inserted, and when we print from top to bottom, we pop top elements.

The sorted stack means top element is largest.

So the sorted stack (top to bottom): 50 40 30 20 10

Let’s do Step 9 carefully:

Stack before insertion: 10 (top), 30

Insert 50:

• top is 10, which is not greater than 50 → pop 10
• next top is 30, which is not greater than 50 → pop 30
• stack empty → push 50
• push back 30
• push back 10

Stack now:
Top → 10, then 30, then 50 (bottom)

Printing top to bottom: 10 30 50

So stack is not sorted this way.

So the stack sorted order after inserting elements means smallest at bottom, largest at top:

This means top is largest.

After all recursion and insertions, final stack will be:

50 (top), 40, 30, 20, 10 (bottom)

which is sorted in ascending order if you read bottom to top.

Summary of how recursion works here

• We remove elements one by one until stack is empty.
• Then we insert elements back in correct sorted order.
• sortedInsert helps put element x in correct position by temporarily popping elements greater than x.
• After insertion, the stack remains sorted from bottom (smallest) to top (largest).

Practice Tip:

To better understand how the stack changes during the sorting process, try adding cout (print) statements inside the functions. For example, print the current elements in the stack each time you push or pop something. This way, you can see step-by-step how elements move in and out of the stack. It helps you visualize the flow of recursion and makes it easier to follow the logic.

Watching the stack change in real time is a great way to learn and debug your code!

Practice Problems

1. Reverse a Stack Using Recursion
   Write a recursive function to reverse the elements of a stack without using any extra stack or array.
2. Insert an Element at the Bottom of a Stack
   Write a recursive function that inserts a given element at the bottom of a stack.
3. Sort a Stack Without Recursion
   Try to sort a stack using only stack operations (push, pop, top) but without recursion. You may use an additional stack or queue.
4. Find the Maximum Element in a Stack Using Recursion
   Write a recursive function that returns the maximum element present in a stack.
5. Delete the Middle Element of a Stack Using Recursion
   Given a stack, write a recursive function to delete the middle element of the stack without using any extra space.

You can also Visit other tutorials of Embedded Prep 

• Structure with Pointers
• Master How to Use a Saleae Logic Analyzer with Arduino Uno (2025)
• Top 30+ I2C Interview Questions
• Bit Manipulation Interview Questions
• Structure and Union in c
• Fault Handling in Arm Cortex Mx Processor
• Merge sort algorithm

Special thanks to @mr-raj for contributing to this article on EmbeddedPrep