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
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
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:
- mid = (i1 + i2) // 2
- recursively sort [i1, mid)
- recursively sort [mid, i2]
- 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