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 `E`s 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 `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.