sort_stack_rec.py

"""
This implementation demonstrates how 
to recursively sort a stack in place.

Let n be the size of the stack.

Time complexity: O(n^2)
Space complexity: O(n)
"""


def sort_stack(stack):
    # base case
    if len(stack) == 0:
        return

    top_element = stack.pop()
    # Pop elements from stack
    sort_stack(stack)

    # Insert them in order into stack
    insert_in_order(stack, top_element)


def insert_in_order(stack, value):
    # Insert value at right position within stack
    if len(stack) == 0 or stack[len(stack)-1] <= value:
        stack.append(value)
        return

    top = stack.pop()
    # Same process all over again but one less element
    insert_in_order(stack, value)

    stack.append(top)


stack = [1, 4, 2, 3]
sort_stack(stack)
print("After sorting:", stack)  # After sorting: [1, 2, 3, 4]