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
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.
- 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.