In [ ]:

```
%config InteractiveShell.ast_node_interactivity="none"
def f(globals, locals):
import base64
code="ZGVmIG1ha2VfcHJpbnRfbG9jYWxzKCk6IAogICAgIyBJbiBhIGZ1bmN0aW9uIHRvIHByZXZlbnQgbG9jYWxzIGFuZCBpbXBvcnRzIGZyb20gbGVha2luZy4KICAgIGdsb2JhbCBtYWtlX3ByaW50X2xvY2FscwogICAgZGVsIG1ha2VfcHJpbnRfbG9jYWxzICAjIE9ubHkgcnVuIHRoaXMgZnVuY3Rpb24gb25jZS4KCiAgICBpbXBvcnQgSVB5dGhvbgogICAgaW1wb3J0IGFzdAogICAgaW1wb3J0IGluc3BlY3QKCiAgICBjbGFzcyBWaXNpdG9yKGFzdC5Ob2RlVmlzaXRvcik6CiAgICAgICAgZGVmIF9faW5pdF9fKHNlbGYpOgogICAgICAgICAgICBzZWxmLnZhcmlhYmxlcyA9IHNldCgpCiAgICAgICAgZGVmIHZpc2l0X05hbWUoc2VsZiwgbmFtZSk6CiAgICAgICAgICAgIHNlbGYudmFyaWFibGVzLmFkZChuYW1lLmlkKQogICAgICAgICMgVE9ETzogUG9zc2libHkgZGV0ZWN0IHdoZXRoZXIgdmFyaWFibGVzIGFyZSBhc3NpZ25lZCB0by4KCiAgICBBTExPV19UWVBFUyA9IFtpbnQsIGZsb2F0LCBzdHIsIGJvb2wsIGxpc3QsIGRpY3QsIHR1cGxlLCByYW5nZV0KICAgIGRlZiBmaWx0ZXJfdmFyaWFibGVzKHZhcmlhYmxlcywgbG9jYWxzKToKICAgICAgICBmb3IgdiBpbiB2YXJpYWJsZXM6CiAgICAgICAgICAgIGlmIHYgaW4gbG9jYWxzIGFuZCB0eXBlKGxvY2Fsc1t2XSkgaW4gQUxMT1dfVFlQRVM6CiAgICAgICAgICAgICAgICB5aWVsZCB2CiAgCiAgICAjIFVuZm9ydHVuYXRlbHksIHRoZXJlIGRvZXNuJ3Qgc2VlbSB0byBiZSBhIHN1cHBvcnRlZCB3YXkgb2YgZ2V0dGluZwogICAgIyB0aGUgY3VycmVudCBjZWxsJ3MgY29kZSB2aWEgdGhlIHB1YmxpYyBJUHl0aG9uIEFQSXMuIEhvd2V2ZXIsIGJlY2F1c2UKICAgICMgd2UgYXJlIGdldHRpbmcgY2FsbGVkIGZyb20gSVB5dGhvbiBpdHNlbGYgYW5kIHdlIGFyZSBhbHJlYWR5IGluc3BlY3RpbmcKICAgICMgdGhlIHN0YWNrdHJhY2UsIHdlIG1pZ2h0IGFzIHdlbGwganVzdCBwZWVrIGludG8gaXRzIGZyYW1lLi4uCiAgICBpZiBJUHl0aG9uLl9fdmVyc2lvbl9fID09ICI1LjUuMCI6CiAgICAgICAgIyBjb2xhYgogICAgICAgIGRlZiBnZXRfYXN0KGZyYW1lKToKICAgICAgICAgICAgcmV0dXJuIGFzdC5Nb2R1bGUoZnJhbWUuZl9iYWNrLmZfYmFjay5mX2xvY2Fsc1sibm9kZWxpc3QiXSkKICAgICAgICBkZWYgZmluZF9sb2NhbHMoZnJhbWUpOgogICAgICAgICAgICByZXR1cm4gZnJhbWUuZl9sb2NhbHMKICAgICAgICBkZWYgYXRfdG9wX2xldmVsKGZyYW1lKToKICAgICAgICAgICAgcmV0dXJuIGZyYW1lLmZfYmFjay5mX2NvZGUuY29fZmlsZW5hbWUuZW5kc3dpdGgoIklQeXRob24vY29yZS9pbnRlcmFjdGl2ZXNoZWxsLnB5IikKCiAgICBlbGlmIElQeXRob24uX192ZXJzaW9uX18gPT0gIjguNC4wIjoKICAgICAgICAjIGxhYiBjb21wdXRlcnMKICAgICAgICBkZWYgZ2V0X2FzdChmcmFtZSk6CiAgICAgICAgICAgIHJldHVybiBhc3QuTW9kdWxlKGZyYW1lLmZfYmFjay5mX2JhY2suZl9sb2NhbHNbIm5vZGVsaXN0Il0pCiAgICAgICAgZGVmIGZpbmRfbG9jYWxzKGZyYW1lKToKICAgICAgICAgICAgcmV0dXJuIGZyYW1lLmZfbG9jYWxzCiAgICAgICAgZGVmIGF0X3RvcF9sZXZlbChmcmFtZSk6CiAgICAgICAgICAgIHJldHVybiBmcmFtZS5mX2JhY2suZl9jb2RlLmNvX2ZpbGVuYW1lLmVuZHN3aXRoKCJJUHl0aG9uL2NvcmUvaW50ZXJhY3RpdmVzaGVsbC5weSIpCiAgICBlbHNlOgogICAgICAgIHByaW50KGYicHJpbnRfbG9jYWxzKCkgbm90IHN1cHBvcnRlZCBvbiBJUHl0aG9uIHZlcnNpb24ge0lQeXRob24uX192ZXJzaW9uX199IikKCiAgICBkZWYgZ2V0X2NlbGxfbmFtZXMoZnJhbWUpOgogICAgICAgIHRyZWUgPSBnZXRfYXN0KGZyYW1lKQogICAgICAgIHZpc2l0b3IgPSBWaXNpdG9yKCkKICAgICAgICB2aXNpdG9yLnZpc2l0KHRyZWUpCiAgICAgICAgcmV0dXJuIGZpbHRlcl92YXJpYWJsZXModmlzaXRvci52YXJpYWJsZXMsIGZyYW1lLmZfbG9jYWxzKQoKICAgIGRlZiBmaW5kX3doaWNoKGZyYW1lKToKICAgICAgICAjIEZyYW1lIGlzIHRoZSBmcmFtZSB3aG9zZSBsb2NhbHMgd2UgYXJlIGludGVyZXN0ZWQgaW4gcHJpbnRpbmcuCiAgICAgICAgaWYgYXRfdG9wX2xldmVsKGZyYW1lKToKICAgICAgICAgICAgIyBUaGUgcGFyZW50IGZyYW1lIG9mIHRoZSBpbnRlcmVzdGVkIGZyYW1lIGlzIGEgbW9kdWxlLCBtb3N0IGxpa2VseQogICAgICAgICAgICAjICJpbnRlcmFjdGl2ZXNoZWxsIi4gVGhpcyBtZWFucyB3ZSBhcmUgaW4gdGhlIGdsb2JhbCBzY29wZSwgc2luY2UKICAgICAgICAgICAgIyBvbmx5IHRoZSBnbG9iYWwgc2NvcGUgc2hvdWxkIGJlIGRpcmVjdGx5IHJ1biBieSB0aGUgaW50ZXJhY3RpdmUgc2hlbGwuCiAgICAgICAgICAgIHJldHVybiBzZXQoZ2V0X2NlbGxfbmFtZXMoZnJhbWUpKQogICAgICAgICMgVGhlIHBhcmVudCBmcmFtZSBpcyBub3QgYSBtb2R1bGUsIHNvIHdlIGFyZSBpbiBhIGxvY2FsIHNjb3BlLgogICAgICAgIHJldHVybiBzZXQoZnJhbWUuZl9sb2NhbHMpCgogICAgZGVmIHByaW50X2xvY2Fscygqd2hpY2gsIHR5cGVzPUZhbHNlKToKICAgICAgICAiIiJQcmludCB0aGUgbG9jYWwgdmFyaWFibGVzIGluIHRoZSBjYWxsZXIncyBmcmFtZS4iIiIKICAgICAgICBpbXBvcnQgaW5zcGVjdAogICAgICAgICMgY3VycmVudGZyYW1lKCkgZnJhbWUgaXMgcHJpbnRfbG9jYWxzLiBXZSB3YW50IHRoZSBjYWxsZXIncyBmcmFtZQogICAgICAgIGZyYW1lID0gaW5zcGVjdC5jdXJyZW50ZnJhbWUoKS5mX2JhY2sKICAgICAgICBsb2NhbHMgPSBmaW5kX2xvY2FscyhmcmFtZSkKICAgICAgICB3aGljaCA9IHNldCh3aGljaCkgaWYgd2hpY2ggZWxzZSBmaW5kX3doaWNoKGZyYW1lKQogICAgICAgIGxsID0ge2s6IHYgZm9yIGssIHYgaW4gbG9jYWxzLml0ZW1zKCkgaWYgayBpbiB3aGljaH0KICAgICAgICBpZiBub3QgbGw6CiAgICAgICAgICAgIHByaW50KCJwcmludF9sb2NhbHM6IG5vIGxvY2FscyIpCiAgICAgICAgICAgIHJldHVybgogICAgICAgIGlmIHR5cGVzOgogICAgICAgICAgICBwcmludCgiXG4iLmpvaW4oZiJ7a306IHt0eXBlKHYpLl9fbmFtZV9ffSDihpAge3Z9IiBmb3IgaywgdiBpbiBsbC5pdGVtcygpKSkKICAgICAgICBlbHNlOgogICAgICAgICAgICBwcmludCgiOyAiLmpvaW4oZiJ7a30g4oaQIHtyZXByKHYpfSIgZm9yIGssIHYgaW4gbGwuaXRlbXMoKSkpCgogICAgcmV0dXJuIHByaW50X2xvY2FscwoKcHJpbnRfbG9jYWxzID0gbWFrZV9wcmludF9sb2NhbHMoKQ=="
exec(base64.b64decode(code), globals, locals)
f(globals(), locals())
del f
def check(fn, *input, expected):
result = fn(*input)
if expected != result:
print(
f"{fn.__name__}({', '.join(input)}) should be {expected}, not {result}.")
else:
print(f"Test case passed!")
```

Let's dance with merge sort! https://www.youtube.com/watch?v=dENca26N6V4

One more for quicksort! https://www.youtube.com/watch?v=3San3uKKHgg

We are going to learn about how Merge Sort works. But first, we are going to figure out how to merge sorted lists of short, fixed sizes, of 4 and 32.

Python3 has a built in sorting function that we can use for parts of this exercise.

Let's say we have two sections of a class. The two sections each contain 16 students. The students are sorted in an alphabetical order based on their names. The lecturer wants to make a grade roster of the entire class. The lecturer wants to retain the alphabetical ordering of the students' names.

Let's take it slower and start with sort2.

In [ ]:

```
# sort2 is a function
sort2 = sorted
def sort4(L):
"""Sorts the list L, which has length 4.
1. Partitions L into two equal halves.
2. Calls the function sort2.
3. Merges the sorted together.
Arguments:
L (List[int]): A (potentially unsorted) list of size 4.
Returns: (List[int]) A sorted list of length 4.
Effects: None.
"""
L_first_sorted = sort2(L[0:2]) # call sort2 on first half
L_last_sorted = sort2(L[2:4]) # call sort2 on second half
#
# do something to return a sorted list
#
```

In [ ]:

```
L = [5, 2, 1, 6]
check(sort4, L, expected = [1, 2, 5, 6])
M = [4, 3, 2, 1]
check(sort4, M, expected = [1, 2, 3, 4])
```

Write a function `sort32`

that sorts a list of 32 elements. The function should make two recursive calls to a provided function `sort16`

In [ ]:

```
sort16 = sorted
def sort32(L):
"""Sorts the list L, which has length 32.
1. Partitions L into two equal halves.
2. Calls the function sort16.
3. Merges the sorted lists together.
Arguments:
L (List[int]): A (potentially unsorted) list of size 32.
Returns: (List[int]) A sorted list of length 32.
Effects: None.
"""
L_first_sorted = sort16(L[0:16])
L_last_sorted = sort16(L[16:32])
#
# do something to return a sorted list
#
```

In [ ]:

```
# TEST_CASE
L = [32, 31, 30, 29, 28, 27, 26, 25, 24, 23, 22, 21, 20, 19, 18,
17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
check(sort32, L, expected = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17,
18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32])
```

Write a function `merge_sort`

that will sort a list of *any* size. The function should make two recursive calls to itself

**Algorithm Merge Sort:** Input `L`

.

We partition the list into two equal halves and sort them by calling the sorting function recursively until we reach the base case where len(L) == 1.

We create a new sorted list by merging the two now sorted halves together and return it.

**For example : for step 2**, if we have L1 = [1, 2, 4] and L2 = [3, 5, 7], we compare 1 from L1 and 3 from L2. 1 is greater, so we add it to the sorted list we are building. Then, we compare 2 from L1 and 3 from L2. 2 is greater, so we add that to the sorted list. Then, we compare 4 from L1 and 3 from L2. 3 is greater, so we add 3 to the sorted list. Then, we compare 4 from L1 and 5 from L2. 4 is greater, so we add it to the sorted list. Now there is no element left in L1, so we add all the remaining elements in L2 to the end of the sorted list.

In [ ]:

```
def merge_lists (L1, L2) :
"""Merges two lists L1 and L2 using the step 2 above.
Arguments: L1 (list), L2 (list)
Returns: (list)
"""
# Merge the two sorted lists : make sure to not leave any element
# Returns the merged list
```

In [ ]:

```
L1 = [1, 4, 5]
L2 = [2, 3, 6]
check(merge_lists, L1, L2, expected = [1, 2, 3, 4, 5, 6])
M1 = [1, 2, 4]
M2 = [3, 5, 7]
check(merge_lists, M1, M2, expected = [1, 2, 3, 4, 5, 7])
N1 = [4, 5]
N2 = [1, 2, 3]
check(merge_lists, N1, N2, expected = [1, 2, 3, 4, 5])
```

In [ ]:

```
def merge_sort(L):
"""Sorts the list L of any size using the merge sort algorithm.
Arguments: L (list)
Returns: (list)
"""
# Base case
# Partition the list into two halves and call the function recursively
# Return the result of merging the two lists, which are now sorted : call the merge_lists function here
```

In [ ]:

```
L = [23, 10, 5, 1, 4]
check(merge_sort, L, expected = [1, 4, 5, 10, 23])
M = [4, 3, 2, 1]
check(merge_sort, M, expected = [1, 2, 3, 4])
N = [-4, 3, 14, 15]
check(merge_sort, N, expected = [-4, 3, 14, 15])
```

Check out this interesting diagram which shows how quicksort divides up an example array:

We are going to try this process ourselves by hand, and then later implement a function which performs quicksort.

When in doubt, try drawing a picture like this with your array.

We are going to quicksort by hand, step by step, the following list of numbers `[10, 15, 1, 2, 6, 12, 5, 7]`

.

- The first step in quicksort is to pick a pivot element, for example
`7`

. - Then, put all elements less than
`7`

on the left of`7`

. - Then, put all elements greater than
`7`

on the right of`7`

.

Note: the array doesn't have to be completely sorted, but `7`

must end up with only items smaller to the left of it.

In [ ]:

```
# Items smaller than 7:
# Items larger than 7:
# All items together, with 7 in-between:
```

Next, we are going to consider each half of our new array, and run merge sort on each half. We are going to divide our arrays again by picking a new pivot for each half.

For the smaller side, we can use the number `5`

.

For the greater side, we will use the number `10`

.

First, write the half of the array that you found earlier, with items less than `7`

.

Now, divide this array based on the new pivot `5`

In [ ]:

```
```

First, write the half of the array you found earlier, with the items greater than `7`

.

Now, divide this array based on the new pivot `10`

In [ ]:

```
```

What happens next, as this process continues? Try to execute the rest of quicksort by hand. When in doubt, try drawing on paper.

This is a useful video which illustrates quicksort:

In [ ]:

```
```

Using quicksort, sort the following list of numbers. Try to write your own quicksort function based on the algorithm given in the lecture (below)

**Algorithm Quicksort:** Input `L`

of length `n`

.

Pick random

`j`

in`[0,...,n-1]`

Let

`pivot=L[j]`

and reorder`L`

so that locations`L[0],..,L[i-1]`

are smaller than`pivot`

and locations`L[i],...,L[n-1]`

are at least as large as`pivot`

.Recursively sort

`L[0],...,L[i-1]`

and`L[i+1],...,L[n-1]`

In [ ]:

```
import random
L = [66, 25, 600, 570, 700, 145, 909, 501, 1000, 10000]
```

`partition`

, which will arrange the list elements in `L`

on the correct side of an integer pivot called `pivot`

.¶The inputs to our function are:

`L`

the list`pivot`

, the pivot element to compare values to`beg`

the

In [ ]:

```
def partition(L, pivot, beg, end):
""".
Arguments: L (list), x (integer), beg (integer), end (integer)
Returns: (tuple)
"""
# move all the elements in L that are less than the pivot to the left of pivot and all the rest to the right of pivot
# return a tuple that represents indices one less than and one greater than the index of the pivot in the list
return (i, j)
```

In [ ]:

```
L = [3, 1, 8, 6, 2, 1, 4]
x1 = 6
beg1 = 0
end1 = len(L) - 1
check(partition, L, x1, beg1, end1, expected = (4, 6))
M = [2, 5, 4, 1]
x2 = 4
beg2 = 0
end2 = len(M) - 1
check(partition, M, x2, beg2, end2, expected = (1, 3))
```

In [ ]:

```
def quicksort(L, beg=0, end=None):
"""Sorts the list L using the quicksort algorithm.
Arguments: L (list)
Returns: (list)
"""
# base case
# select a pivot randomly
# run the partition on that pivot
```

In [ ]:

```
check(quicksort, L, expected = ['Arsenal', 'Chelsea', 'Crystal Palace', 'Leicester', 'Liverpool', 'Man City', 'Man United', 'Southampton', 'Tottenham'])
# for other inputs
M = [23, 10, 5, 1, 4]
check(quicksort, M, expected = [1, 4, 5, 10, 23])
N = [4, 3, 2, 1]
check(quicksort, N, expected = [1, 2, 3, 4])
O = [-4, 3, 14, 15]
check(quicksort, O, expected = [-4, 3, 14, 15])
```

Using your quicksort algorithm, sort the following list of football teams based on their points.

In [ ]:

```
L = [["Man United", 10],
["Leicester", 3],
["Chelsea", 6],
["Tottenham", 5],
["Arsenal", 7],
["Liverpool", 9],
["Southampton", 1],
["Man City", 10],
["Crystal Palace", 9]]
# write your code here
```