Operations in Stack
- Push(): Pushes an element into the stack
- Pop(): Pops out the top element of the stack
- Top(): Returns the top element of the stack
- Size(): Returns the size of the stack
Why Do We Need To Sort A Stack?
As mentioned in the earlier parts stack is a very useful and important data structure that is used in memory management and in the scheduling of process flow. One of the most essential uses of the stack is the program counter stores the context of a processor code to stack whenever it has to switch to a new process so that it can return back to the previous process and complete it after completing the new process.
Now, most of the times these process context needs to be sorted by their priorities for processing and hence sorting has a beneficial application in it.
Now we can do this sorting iteratively too but, in this article, we will be using Recursion.
What is Recursion?
It’s one of the most important algorithms which makes use of the property that if we can solve a smaller job then we can definitely do the complete job by using the smaller jobs. Recursion basically means to call itself. It has a base case, the main case of handling the smaller problem case and then calling itself for the smaller parts.
It uses the fact that whenever we are standing on a particular state, we assume that our recursive function has completed processing for smaller answers, and now we can combine those to get the answer of our current state.
Basic Structure of Recursion
Void Recursion_function(int somedata){
// Base case
Some condition
//recursive call to itself
Recursion_function( smaller-somedata);
}
How to Sort a Stack Using Recursion?
Well, the idea is quite intuitive and easy. We can recursively pop out each of the elements of the stack and then call a recursive function to insert the elements again in the stack in sorted order.
Let us see the algorithm:
While the stack is not empty
Int top = stack top();
Stack pop();
sortStack(); // keep on poping the elements until the stack is empty
sortedInsert( top ); // when the stack is now empty or sorted already inserted in sorted order
SortedInsert() // sorted insert function
If the stack is empty or the stack top < current element
Stack push (current element)
Else {
Top = stack top;
Stack pop();
sortedInsert();
stack push(current element );
}
Visual Working
1. First Iteration keeps on calling the recursive function to pop out the top element until the stack is empty.
- Top element = 6 (Top in the stack frame #1)
- Top element = -3 (Top in the stack frame #2)
- Top element = 23 (Top in the stack frame #3)
- Top element = 12 (Top in the stack frame #4)
-
Top element = -1 (Top in the stack frame #5)
2. Now the program gets to the stack frame of the final element i.e. -1 and correspondingly calls the sorted insert function. The stack becomes,

3. It gets to the next stack frame i.e. #4 and the current element now is 12, stack top is -1, as 12 > -1, 12 will directly be inserted in the stack.

4. For the next iteration current element is 23, stack top is 12 hence push it again directly.

5. Now current element is -2 and the stack top is 23 and -2 < 23 hence the new top will be stored and it will recursively call the sortedinsert function with the current -2 until it gets to an element where the stack top is smaller than -2 or the stack becomes empty and then push it.

6. Push back all the elements in top after the previous element has been placed in its right place.

7. The above step gets repeated for the next element also and the final stack becomes.

We get the final sorted stack.
Also read about Learning Recursion in C++
Code Implementation
Here I will be using C++ STL to implement a recursive stack.
C++
#include<bits/stdc++.h>
using namespace std;
void sortedInsert(stack<int> &st,int element){
if(st.empty() || element > st.top())
st.push(element);
else{
int top_element = st.top();
st.pop();
sortedInsert(st,element);
st.push(top element);
}
}
void sortStack(stack<int> &st){
if(!st.empty()){
int top_element = st.top();
st.pop();
sortStack(st);
sortedInsert(st,top_element);
}
}
int main(){
stack<int> st;
int n;
cin>>n;
while (n--){
int x;
cin>>x;
st.push(x);
}
sortStack(st);
while(!st.empty()){
int top = st.top();
st.pop();
cout<<top<<endl;
}
return 0;
}

You can also try this code with Online C++ Compiler
Run Code
Time Complexity: O(n^2) Space Complexity: O(n) for the auxiliary space stack


Must Read Stack Operations
Frequently Asked Questions
How would you use recursion to sort a stack?
To sort a stack using recursion, pop elements, recursively sort the rest, then insert the popped element at the correct position. Repeat until the stack is sorted.
Why the space complexity of recursion is always at least O(n) ?
Recursion function calls itself multiple times and this is done internally by using function call stack which is again a definitive application of stack. So, this stack again stores some and hence the space complexity is minimum O(n).
How the time complexity of a recursive function calculated?
Most of the recursive function calls itself multiple times which means for every function call, we will always have the function calls of it’s subproblems. This means for ‘n’ function calls we will have ‘n’ calls again to insert the elements again in this case: O(n^2).
What do stacks have to do with sorting?
Stacks are crucial in algorithms like quicksort. They provide a Last In First Out (LIFO) structure, facilitating efficient sorting algorithms and recursion.
Conclusion
Sorting a stack using recursion is a fascinating and efficient algorithmic technique. By leveraging the principles of recursion and the stack's Last In First Out (LIFO) nature, we can achieve a sorted stack. This approach offers a clear illustration of how recursion and stack data structures can be harmoniously applied to solve a common problem. Hope this article has cleared your understanding of stacks and how to sort them using recursion.
Recommended Problems: