Can you sort a stack in ascending order (with biggest items on top)?

You can sort a stack in ascending order (with biggest items on top) using another temporary stack. The idea of the sorting algorithm is to pull an item from the original stack and push it on the other stack. If pushing this item would violate the sort order of the new stack, you need to remove enough items from it and push them back on the original stack before pushing the new item. The popped elements from the temporary stack which are greater than the element to be inserted are kept in recursion and then we call insert to insert the new element in the temporary (or auxiliary) stack in its rightful place.

Here’s the algorithm in detail:

1. Create an empty ‘auxiliary‘ stack.

2. While the original stack is not empty:

- Pop an element from the original stack, call it ‘temp‘.

- While the ‘auxiliary‘ stack is not empty and the top of the ‘auxiliary‘ stack is less than ‘temp‘, pop from ‘auxiliary‘ and push back to the original stack. Repeat this step until the condition is false.

- Push ‘temp‘ into ‘auxiliary‘.

3. The ‘auxiliary‘ stack now contains the original stack’s elements sorted such that the largest element is at the top of the stack.

Here is the pseudo-code for the above algorithm:

def sortedInsert(s, element):
    if len(s) == 0 or element > s[-1]:
        s.append(element)
        return
    temp = s.pop()
    sortedInsert(s, element)
    s.append(temp)

def sortStack(s):
    if len(s)!= 0:
        temp = s.pop()
        sortStack(s)
        sortedInsert(s, temp)

# main
s = []
s.append(3)
s.append(5)
s.append(1)
s.append(4)
s.append(2)
sortStack(s)

In above pseudo-code, sortStack function is a recursive function and sortedInsert function is also a recursive function used to insert the popped items back to the ‘auxiliary‘ stack (‘s‘ in this case) at correct positions.

This algorithm has a time complexity of O(n²). For each element, it’s popped once from the original stack and then pushed once in the ‘auxiliary‘ stack. For every insertion, we may pop from ‘auxiliary‘ stack and push it back up to n times. Hence the total time complexity is O(n) for pop and push operations and O(n²) for insert operation and hence O(n²) in total.