Sort Stack

Write a program to stort a stack such that the smallest items are on the top. You can use an additional temporary stack, but you may not copy the elements into any other data structure (such as an array). The stack supports the following operations : push, pop, peek and isEmpty.

Solution

We can implement a simple insertion sort by popping elements off of the main stack, and inserting them in the proper location in the temporary stack. In order to insert the elements in the middle of the temporary stack, we will need to pop elements off of the temporary stack. We can store these elements in the original stack, and since they are in sorted order, we can then move them back to the temporary stack.

After the temporary stack is sorted in reverse order, we can reverse it onto the original stack.

def sort_stack(stack):
  r_stack = Stack()

  while(not stack.is_empty()):
    value = stack.pop()

    if(r_stack.is_empty()):
      r_stack.push(value)

    else:
      while(not r_stack.is_empty() and r_stack.peek() > value):
        tmp = r_stack.pop()
        stack.push(tmp)

      r_stack.push(value)

  while(not r_stack.is_empty()):
    value = r_stack.pop()
    stack.push(value)