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

From "Deciphering the coding interview":

Write a program to sort a stack in ascending order (with the largest items at the top). You can use at most one additional stack to contain items, but you cannot copy the items into any other data structure (such as an array). The battery supports push, pop, is_emptyY peek

So, the classic solution I found online for this (and the one in the book) is something like this:

Something # 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 essence of this is that we will return our secondary / auxiliary battery after ordering by time O (n ^ 2).

However, this is not my initial approach, and I think my approach has some interesting qualities:

Something # 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 so clean or elegant, but it could be with some auxiliary functions that dynamically choose our comparator and choose which element to push, etc.

Basically what he 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 / worst case compromise solution.
Something # 1 really does worst when the battery is already sorted and better when the battery is ordered in the wrong order, and something # 2 does the opposite.

Questions

  • What are your thoughts? I think it's an interesting way to order that I haven't seen before.
  • Is there a name for this type of classification? I couldn't find something similar, but I'm sure they are out there and I would love to describe / recognize it better. Thank you!