This notebook was prepared by Donne Martin. Source and license info is on GitHub.

- When sorted, should the largest element be at the top or bottom?
- Top

- Can you have duplicate values like 5, 5?
- Yes

- Can we assume we already have a stack class that can be used for this problem?
- Yes

- Can we assume this fits memory?
- Yes

- Empty stack -> None
- One element stack
- Two or more element stack (general case)
- Already sorted stack

Refer to the Solution Notebook. If you are stuck and need a hint, the solution notebook's algorithm discussion might be a good place to start.

In [ ]:

```
%run ../stack/stack.py
%load ../stack/stack.py
```

In [ ]:

```
class MyStack(Stack):
def sort(self):
# TODO: Implement me
pass
```

**The following unit test is expected to fail until you solve the challenge.**

In [ ]:

```
# %load test_sort_stack.py
from random import randint
import unittest
class TestSortStack(unittest.TestCase):
def get_sorted_stack(self, stack, numbers):
for x in numbers:
stack.push(x)
sorted_stack = stack.sort()
return sorted_stack
def test_sort_stack(self, stack):
print('Test: Empty stack')
sorted_stack = self.get_sorted_stack(stack, [])
self.assertEqual(sorted_stack.pop(), None)
print('Test: One element stack')
sorted_stack = self.get_sorted_stack(stack, [1])
self.assertEqual(sorted_stack.pop(), 1)
print('Test: Two or more element stack (general case)')
num_items = 10
numbers = [randint(0, 10) for x in range(num_items)]
sorted_stack = self.get_sorted_stack(stack, numbers)
sorted_numbers = []
for _ in range(num_items):
sorted_numbers.append(sorted_stack.pop())
self.assertEqual(sorted_numbers, sorted(numbers, reverse=True))
print('Success: test_sort_stack')
def main():
test = TestSortStack()
test.test_sort_stack(MyStack())
try:
test.test_sort_stack(MyStackSimplified())
except NameError:
# Alternate solutions are only defined
# in the solutions file
pass
if __name__ == '__main__':
main()
```

Review the Solution Notebook for a discussion on algorithms and code solutions.