Week 12: Sorting

Today we’ll learn implement some sorting algorithms on arrays.

Merge sort

The merge sort algorithm is simple:

1. Split the input sequence in half (one may be one element longer).
2. Recursively merge sort each half of the list.
3. Merge the remaining lists.

Note that this sort is in-place, i.e., we won’t return anything, we’ll just update the sequence. In pseudocode:

mergesort(l):
  split l arbitrarily into two parts, l1 and l2, of nearly equal length
  l1_sorted = mergesort(l1)
  l2_sorted = mergesort(l2)
  merge(l1_sorted, l2_sorted) # we'll change this in a moment

All that remains is defining the merge function. In its simplest form, merge takes two arrays and returns a new one. But it’s easiest in Java (and saves some allocation) to instead take an extra out parameter, where we’ll write our list. Then we have pseudocode:

merge(l, r, out):
  assert out.length == l1.length + l2.length # out needs to be the right size!

  iL = 0
  iR = 0
  
  for i = 0 to out.length, exclusive:
    if iL is in-bounds for l and l[iL] <= r[iR]:
      out[i] = l[iL]
      iL += 1
    else:
      out[i] = r[iR]
      iR += 1

mergesort(l):
  split l arbitrarily into two parts, l1 and l2, of nearly equal length
  l1_sorted = mergesort(l1)
  l2_sorted = mergesort(l2)
  merge(l1_sorted, l2_sorted, l) # reuse the original sequence as the out

To implement things in Java, we have a tricky problem: it’s not possible, in general, to allocate arrays of generic types. Oops! The easy solution here is:

1. Use an explicit Comparator<E> called c. You can call c.compare(a, b) and get a result like compareTo from Comparable.
2. Use Arrays.copyOfRange to get the sub-sequences.

Go ahead and implement this algorithm. Here’s an interface:

public class Sorting {
  public static <E> void merge(E[] l, E[] r, E[] out, Comparator<E> c);
  public static <E> void mergeSort(E[] a, Comparator<E> c);
}

Test your code on a variety of lists. It may be easier to test merge first. A good way to test is to make list of 256 random integers; call mergeSort on each one and make sure the result is sorted.

Quicksort

Quicksort is a deceptively simple algorithm. It seems straightforward, but it’s very easy to mess up and have it run forever or not quite sort your elements.

Here’s the general idea: you quicksort an array a of Es in some range between lo and hi (inclusive), given a Comparator<E> c.

1. If lo >= hi or hi < 0 or hi >= a.length, you’re done.

2. Partition a between lo and hi, using the comparator c, to find a split-point split.

   a. You’ll need to pick a pivot. For now, it’s probably easiest to pick the middle of the range from lo to hi.

   b. Increment the lo index until you find an element greater than or equal to the pivot (according to c).

   c. Decrement the hi index until you find an element greater than or equal to the pivot (according to c).

   d. If lo >= hi, return the split-point hi.

   e. Swap the inverted elements.

   f. Increment the lo and hi elements, and go back to (b).

3. Recursively run quick sort on a from lo to split with c.

4. Recursively run quick sort on a from split + 1 to hi with c.

The hard part here is the partition function. It’s very, very subtle! Tiny differences in comparisons will cause challenging bugs. Using the debugger is very helpful; I also recommend putting in assertions and print statements to make it clear what is happening when. (The Lomuto partition scheme is slightly slower in practice, but may be easier to implement.)

Go ahead and implement quick sort. Here’s an interface:

public class Sorting {
  // ...

  public static <E> void quickSort(E[] a, Comparator<E> c);
  public static <E> void quickSort(E[] a, int lo, int hi, Comparator<E> c);
  public static <E> int partition(E[] a, int lo, int hi, Comparator<E> c);
}

The first quickSort(E[], Comparator<E>) should just call quickSort(E[], Comparator[], int, int) with 0 and a.length - 1, respectively.

I recommend writing a few simple test cases to shake out simple bugs… but random testing will really help here. Use a for-loop to initial an array of Integers with random values, sort the array, and make sure things are sorted. If you can run the loop a few thousand times on a long array, you should be good.