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

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.
• Honestly the question isn't solvable if read in it's most strict form. A single temp variable is technically a data structure so you unless you are allowed to swap the top elements you can only scan along them. Commented Sep 19, 2019 at 11:30
• couldn't find similar [algorithms] alternating sort order has been used in "read backwards tape sort" for a long time. Commented Sep 28, 2019 at 10:09

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' $$$$
`