Overview / Logistics

Click here to download the starter code for today.

We've seen some quadratic algorithms for searching that use loops. Today, we're going to work on implementations of two recursive "divide and conquer" techniques, which are more efficient either in theory, in practice, or both.

Merge Sort

The first sort is merge sort, which we saw in Module 14. You should fill in mergesort.py to do implement this sort. To recap, the steps are as follows:

1. Split the array into two halves, and sort each half recursively
2. Merge the two halves together, using a temporary array as a staging area.

The recursive setup in step 1 has been provided for you. Your job will to fill in the merging step, which is where the meat of the work occurs on each recursive call

Quick Sort

Quick sort is another recursive sort that takes a slightly different approach. Instead of completely sorting two halves and then merging them, it first chooses what's known as a pivot, which is just some element in the array. It then moves everything that's less to the pivot to the left of the array, and everything to the right of the pivot to the right of the array. It then recursively sorts the chunk to the left of the pivot and to the right of the pivot. Below is an animation, courtesy of Wikipedia

The advantage of this algorithm is that it does not require an auxiliary array as a staging area; it is an in-place sort. However, the theoretical worst case behavior is worse, which we will analyze