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_empty`

Y `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!