An alternative algorithm for sorting a stack using only one additional stack

Question

From "Cracking the Coding Interview":

Write a program to sort a stack in ascending order (with biggest items on top). You may use at most one additional stack to hold items, but you may not copy the elements into any other data structure (such as an array). The stack supports push, pop, is_empty, and peek

The classic solution I found online to this (and the one in the book) is something like this:

Algo #1 (Classic)

 def sort_stack(primary):
   secondary = []
   while primary:
     tmp = primary.pop()
     while (secondary and secondary[-1] > tmp):
       primary.append(secondary.pop())
     secondary.append(tmp)
   return secondary

The gist of this being that we will return our secondary/auxiliary stack after sorting via \$O(n^2)\$ time.

This is not what my initial approach was, however, and I do think my approach has some interesting qualities:

Algo #2 (Mine)

def sort_stack(primary):
  did_sort = False
  secondary = []
  while not did_sort:
    # move from primary to secondary, pushing larger elements first when possible
    desc_swap(primary, secondary)
    # move from secondary back to primary, pushing smaller elements first when possible. Set did_sort = True if we're done and can exit.
    did_sort = asc_swap(secondary, primary)
  return primary

def asc_swap(full, empty):
  temp = None
  did_sort = True
  yet_max = None

  while full:
    if not temp:
      temp = full.pop()
    if full:
      if full[-1] < temp:
        insert = full.pop()
        if insert < yet_max:
          did_sort = False
        yet_max = insert
        empty.append(insert)
      else:
        empty.append(temp)
        temp = None
  if temp:
    empty.append(temp)
  return did_sort


def desc_swap(full, empty):
  temp = None
  while full:
    if not temp:
      temp = full.pop()
    if full:
      if full[-1] > temp:
        empty.append(full.pop())
      else:
        empty.append(temp)
        temp = None
  if temp:
    empty.append(temp)

Now obviously it is not nearly as clean or elegant, but it could be with some helper functions that dynamically choose our comparator and choose which element to push, etc.

Basically what it is doing is this:

# Start with stack in wrong order (worst case)
primary:   4 3 2 1
secondary:  

# Swap to secondary, pushing larger elements first (1 is held in temp until the end because it is smaller than the following elements)
primary:    
secondary: 2 3 4 1

# Swap back to primary, pushing smaller elements first
primary:   1 3 2 4
secondary:  

# back to secondary 
primary:   
secondary: 4 3 2 1

# Back to primary, finished
primary:   1 2 3 4
secondary:

This strategy has a best-case/worst-case tradeoff. Algo #1 actually performs worst when the stack is already sorted and best when the stack is sorted in the wrong order, and algo #2 does the opposite.

Questions

• What are your thoughts? I think it is just an interesting way to sort that I haven't seen before.
• Is there a name for this kind of sorting? I couldn't find similar algos but I'm sure theyre out there and would love to be able to describe it/recognize it better.

Answer 1

I really don't recommend trying to write anything that is more complicated than necessary during an interview, especially if it's on a whiteboard. Interviews are stressful enough for you; introducing more opportunities for errors is not a good idea. As for the interviewer, their likely thoughts are that your code lacks elegance and is hard to verify.

In this case, your code is buggy and crashes for sort_stack([3, 1, 4, 1]) on line 22, in asc_swap:

    if insert < yet_max:
TypeError: '<' not supported between instances of 'int' and 'NoneType' `