Overview / Logistics

The purpose of this lab is to get you practice with sorting algorithms and recursion. It will also warm you up for the next assignment on fair voting and rank aggregation

Click here to download the starter code for this lab. When you are finished, upload your sort.py file to canvas.

Part 1: Merge Sort (3 Points)

Fill in the mergesort_rec and merge methods in sort.py to complete a merge sort implementation Click here to review how this works.

A recursive call to merge sort puts the elements between indices i1 and i2 in order by breaking this range into half, sorting each half individually, and merging the sorted versions together. Pictorially, the sorted region looks like this:

The recursive pseudocode for merge sort is as follows:

1. mid = (i1 + i2) // 2
2. recursively sort [i1, mid)
3. recursively sort [mid, i2]
4. Merge these two together

You will also have to consider a base case. Then, if you implement the merge method and put this all together, you should end up with a sorted array.

Note: Your solution should run in O(N log N) time and use O(N) memory. Our textbook presents a solution that uses O(N log N) time and O(N log N) memory with very succinct code using slices, but I want us to be more careful.

Part 2: Kendall Tau Comprehension Questions

Click here to answer a couple of questions about Kendall-Tau