Week 12: Sorting
Today we’ll learn implement some sorting algorithms on arrays.
Merge sort
The merge sort algorithm is simple:
 Split the input sequence in half (one may be one element longer).
 Recursively merge sort each half of the list.
 Merge the remaining lists.
Note that this sort is inplace, 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 inbounds 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:
 Use an explicit
Comparator<E>
calledc
. You can callc.compare(a, b)
and get a result likecompareTo
fromComparable
.  Use
Arrays.copyOfRange
to get the subsequences.
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 E
s in some
range between lo
and hi
(inclusive), given a Comparator<E> c
.

If
lo >= hi
orhi < 0
orhi >= a.length
, you’re done. 
Partition
a
betweenlo
andhi
, using the comparatorc
, to find a splitpointsplit
.a. You’ll need to pick a pivot. For now, it’s probably easiest to pick the middle of the range from
lo
tohi
.b. Increment the
lo
index until you find an element greater than or equal to the pivot (according toc
).c. Decrement the
hi
index until you find an element greater than or equal to the pivot (according toc
).d. If
lo >= hi
, return the splitpointhi
.e. Swap the inverted elements.
f. Increment the
lo
andhi
elements, and go back to (b). 
Recursively run quick sort on
a
fromlo
tosplit
withc
. 
Recursively run quick sort on
a
fromsplit + 1
tohi
withc
.
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 Integer
s 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.