Recursive solution to sort a stack

Given a stack, sort it using recursion. The use of any other data structures (like containers in STL or Collections in Java) is not allowed.


 

For example,


Stack before sorting :  5 | -2 | 9 | -7 | 3     where 3 is the top element
Stack after sorting  : -7 | -2 | 3 |  5 | 9     where 9 is the top element

 

 
The idea is very simple. We recursively remove values from the stack until the stack becomes empty and then insert those values (from call stack) back into the stack in sorted position. Below is C++ and Java implementation of the idea:

C++

Download   Run Code

Output:

Stack before sorting : 3 -7 9 -2 5
Stack after sorting  : 9 5 3 -2 -7

Java

Download   Run Code

Output:

Stack before sorting : [5, -2, 9, -7, 3]
Stack after sorting  : [-7, -2, 3, 5, 9]

 
The time complexity of above solution is O(n2) and requires O(n) extra space for the call stack where n is the number of elements in the stack.

 
Thanks for reading.

Please use our online compiler to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 


Leave a Reply

avatar
  Subscribe  
newest oldest most voted
Notify of
Anshul
Guest

Awesome