Sort a Stack-Recursion

DSA for Interview Prep

This problem might look very simple to you, but it isn't. It is one of the best problems to understand recursion in depth once you have studied the more basic applications.

How would you react to this problem in an interview?

The first thing is to remain calm. That will help you think better. Let’s try to observe behaviour. Let's say we pop an element from the top of the stack. Now you look at the top of the stack. Is it smaller or greater than the popped element? If greater, than that is what you want, you can insert it on the top. But this is just the top 2. You need to go down all the way to the last element at the bottom of the stack.

So at every recursion, pop the top element and call the recursion with this element again. Now let's say we have popped all but one element from the stack, and now we can insert it all back. For this, we will need another recursive function. So insert will also be recursive.

You keep going till your element is greater than the top of the stack but less than the previous element. Let the stack be — [2, 3, 5, 6] and you want to insert 4. So at every step, you check if 4 is greater than the top of the stack, if not, pop the top of the stack, store it and call the insert function recursively with the leftover elements in the stack. One driving thought here is if at any point the element to insert is greater than the top of the stack, it is greater than all others. That’s what the recursive insert and sort does. You start from the last two elements and keep building.

What will be the time complexity? Exponential?

The time complexity of the sortStack function is O(n^2), where n is the number of elements in the stack. This is because the sorting algorithm used is a recursive implementation of insertion sort.

Let’s break down the time complexity:

sort(stack)

• In the worst case, the sort function makes n recursive calls, where n is the number of elements in the stack.
• In each recursive call, it pops an element from the stack and makes a recursive call.
• The recursive calls continue until the stack is empty, and each call involves popping one element.
• Therefore, the time complexity for the sort function is O(n).

insert_sorted_stack(stack, x)

• In the worst case, the insert_sorted_stack function makes recursive calls until it finds the correct position to insert the element x.
• The number of recursive calls in the worst case is proportional to the number of elements greater than x already in the stack.
• In the worst case, the function may make approximately n/2 recursive calls, leading to a time complexity of O(n) for the insert_sorted_stack function.

Here is the code:

from os import *
from sys import *
from collections import *
from math import *

def sortStack(stack):
    # given data structure is a python list 
    # as list have all the similar operations available so use them
    # Write your code here

    def sort(stack):
        if len(stack)==1:
            return
        x = stack.pop()
        sort(stack)
        insert_sorted_stack(stack,x)
        return

    def insert_sorted_stack(stack,x):
        if len(stack)==0 or x>=stack[-1]:
            stack.append[x]
            return
        else:
            temp_pop = stack.pop()
            insert_sorted_stack(stack, temp_pop)
            stack.append(x)

    return sort(stack)

Thats it! You did it! A few things to keep in mind are the return statements. Where you place them is important. Use append and pop, not push and pop. That’s it! This is nested recursion, a very interesting concept!

I tried this problem on Code Studio, a platform by Coding Ninjas:

Coding Ninjas Studio

That’s it for this article! Feel free to leave feedback or questions in the comments.

Enjoyed the article and found it helpful. If you’d like to show your appreciation and support my work, you can follow and share my articles!

My country does not support the Medium Partner program yet. Hence, it would mean the world to me if you guys, my readers, could support me!

Your support goes a long way in helping me create more content like this. Thank you in advance! ☕️