How to sort a stack using recursion

The stack is a linear data structure that follows a particular order to store data (LIFO).

In this answer, we'll learn to sort a stack using recursion. The example below demonstrates this visually.

Note: To learn more about the Stack data structure, refer to this link.

Simple method

A simple way to do this is by creating a temporary stack. This method will involve the following steps:

1. Create a temporary stack temp_stack.

2. Repeat this process until the input stack gets empty.

3. Pop an element from the input stack and store it in a temp_var.

4. While the temp_stack is not empty && the top of the temp_stack < temp_var , pop an element from temp_stack and push it into the input stack.

5. Push back temp_var to the temp_stack.

6. Return temp_stack.

However, we'll make a recursive solution in order to sort the given stack. For this, it is helpful to recall how recursion works.

Recursive solution

Instead of storing the popped element in a separate, explicitly defined, and created stack, we can hold all the values of the stack in a function call stack. A recursive solution allows separate copies of this variable to be stored. It will hold all the values of the stack in a function call stack until it becomes empty. After this, insert all items one by one in sorted mean. The important thing in this method is sorted order while insertion.

The following illustration shows the stack frame by popping all elements from the input stack:

The input stack is empty now and the function insert_in_sorted_order() will insert elements from the stack frame to the input stack in the following sequence:

1. It inserts 30 from stack frame #5 to the bottom of the input stack.

2. It inserts -5 from stack frame #4 since -5 < 30 to the bottom of the input stack.

3. It inserts 18 below 30 from stack frame #3, since -5 < 18 < 30.

4. It inserts 14 below 18 from stack frame #2, since 14 < 18 < 30.

5. Finally, it inserts -3 below 14 from stack frame #1, since -3 < 14 < 18 < 30.

The visual demonstration of our solution is shown below:

Code example

The code below implements the insert_in_sorted_order() functions using the traditional push, pop, and top functions of the stack :

Code explanation

The highlighted lines of code implement the two functions discussed, while the rest of the code is in the class definition of our stack and its main operations. These highlighted lines are explained below:

• Lines 3–18: We implement the insert_in_sorted_order( ) function in the following steps:

  • Pop an element from the original stack and store it in temp.

  • Once our original stack has been emptied, push temp onto it.

  • During backtracking of this recursive function, push each temp back onto our original stack using the sorted order.

• Lines 21–34: We implement the sortStack( ) function in the following steps:

  • Pop an element from the top of the original stack and store it in a variable e.

  • Sort the remaining elements of the stack recursively. Do the same for the rest of the stack and push this element back into the original stack by calling insert_in_sorted_order( ).

Time complexity

The time complexity of this algorithm is $O(n^2)$ because the worst case of sortstack( ) and insert_in_sorted_order( ) is called for $n$ times for putting elements in their right place, where $n$ is the number of elements of the input stack.