Sorting II: merge sort, quick sort, heap sort

The three algorithms of week 13 are O(n²): about 10¹² steps for a million elements, hours. This week we come down to O(n log n) with the idea of divide and conquer: the same million elements take 2 · 10⁷ steps, under a second. There are two main algorithms: merge sort does its work in the merge step, quick sort does its work in the partition step. The third is heap sort, which uses the heap, the data structure of the next course; here we see its general idea. The exam asks for the order of the merge steps, the partition trace and the comparison table.

Golden rules:

1. Merge sort: divide (easy), combine (the real work). O(n log n) in every case, O(n) extra memory, stable.
2. Quick sort: partition (the real work), no combine. Average O(n log n), O(n²) with a bad pivot.
3. After the partition the pivot is in its final place. The two sides are unsorted within themselves.
4. When writing the trace, check which partition scheme is used. On this page it is Lomuto, pivot = last element.

Merge sort

The idea: an array of one element is already sorted. Split the array into two, sort each half (by recursion), then merge the two sorted halves.

static void mergeSort(int[] a, int[] tmp, int lo, int hi) {
    if (lo >= hi) return;               // 0 or 1 element
    int mid = (lo + hi) / 2;
    mergeSort(a, tmp, lo, mid);
    mergeSort(a, tmp, mid + 1, hi);
    merge(a, tmp, lo, mid, hi);
}

static void merge(int[] a, int[] tmp, int lo, int mid, int hi) {
    int i = lo, j = mid + 1, k = lo;
    while (i <= mid && j <= hi) {
        if (a[i] <= a[j]) tmp[k++] = a[i++];
        else              tmp[k++] = a[j++];
    }
    while (i <= mid) tmp[k++] = a[i++];
    while (j <= hi)  tmp[k++] = a[j++];
    for (k = lo; k <= hi; k++) a[k] = tmp[k];
}

merge is the array version of the merge we wrote on a linked list in week 4. The difference: in an array you can’t merge in place, you write into an auxiliary array (tmp) and copy back.

Trace: {38, 27, 43, 3, 9, 82, 10}

                [38, 27, 43, 3, 9, 82, 10]
               /                          \
      [38, 27, 43, 3]                [9, 82, 10]
       /          \                   /        \
   [38, 27]     [43, 3]           [9, 82]      [10]
    /    \       /   \             /   \
  [38]  [27]   [43]  [3]         [9]  [82]

The merges (program output, in the order they happen):

merge [38] + [27] -> [27, 38]
merge [43] + [3] -> [3, 43]
merge [27, 38] + [3, 43] -> [3, 27, 38, 43]
merge [9] + [82] -> [9, 82]
merge [9, 82] + [10] -> [9, 10, 82]
merge [3, 27, 38, 43] + [9, 10, 82] -> [3, 9, 10, 27, 38, 43, 82]
[3, 9, 10, 27, 38, 43, 82] comps=14

PITFALL · The merge order is not level by level. The recursion finishes the left side entirely and then moves right. The merge of [9, 82] comes after [3, 27, 38, 43] has been formed. If you write “first merge all the pairs”, the order is wrong (that is the order of bottom-up merge sort).

Complexity

$T(n) = 2T(n/2) + n$ → $O(n \log n)$ (week 11). Since the split is always in the middle, best, average and worst are the same. In a single merge the number of comparisons is at least the size of the smaller half and at most $n_1 + n_2 - 1$:

merge [1, 2, 3, 4] + [5, 6, 7, 8] -> [1, 2, 3, 4, 5, 6, 7, 8]
comps=4
merge [1, 3, 5, 7] + [2, 4, 6, 8] -> [1, 2, 3, 4, 5, 6, 7, 8]
comps=7

Quick sort

The idea: choose a pivot. Rearrange the array so that the elements smaller than the pivot are on the left and the larger ones on the right (partition). The pivot is now in its final place. Sort the left and right sides by recursion. There is no combine step; everything ends up in place.

Lomuto partition (pivot = last element)

static int partition(int[] a, int lo, int hi) {
    int pivot = a[hi];
    int i = lo - 1;                 // end of the smaller region
    for (int j = lo; j < hi; j++) {
        if (a[j] < pivot) {
            i++;
            int t = a[i]; a[i] = a[j]; a[j] = t;
        }
    }
    int t = a[i + 1]; a[i + 1] = a[hi]; a[hi] = t;   // put the pivot in place
    return i + 1;
}

static void quickSort(int[] a, int lo, int hi) {
    if (lo >= hi) return;
    int p = partition(a, lo, hi);
    quickSort(a, lo, p - 1);
    quickSort(a, p + 1, hi);
}

The first partition on {7, 2, 9, 4, 3, 8, 5}, step by step:

pivot=5 start [7, 2, 9, 4, 3, 8, 5]
j=0 a[j]>=pivot, skip     [7, 2, 9, 4, 3, 8, 5]
j=1 a[j]<pivot, i=0 swap -> [2, 7, 9, 4, 3, 8, 5]
j=2 a[j]>=pivot, skip     [2, 7, 9, 4, 3, 8, 5]
j=3 a[j]<pivot, i=1 swap -> [2, 4, 9, 7, 3, 8, 5]
j=4 a[j]<pivot, i=2 swap -> [2, 4, 3, 7, 9, 8, 5]
j=5 a[j]>=pivot, skip     [2, 4, 3, 7, 9, 8, 5]
place pivot at 3 -> [2, 4, 3, 5, 9, 8, 7]

During the loop the array is divided into four regions:

[ lo .. i ]     < pivot
[ i+1 .. j-1 ]  >= pivot
[ j .. hi-1 ]   not yet looked at
[ hi ]          pivot

The whole sort:

partition [0..6] pivot 5 at 3 -> [2, 4, 3, 5, 9, 8, 7]
partition [0..2] pivot 3 at 1 -> [2, 3, 4, 5, 9, 8, 7]
partition [4..6] pivot 7 at 4 -> [2, 3, 4, 5, 7, 8, 9]
partition [5..6] pivot 9 at 6 -> [2, 3, 4, 5, 7, 8, 9]
[2, 3, 4, 5, 7, 8, 9] comps=11

TIP · Other partition schemes. Textbooks and some instructors take the first element or the median of three elements (median-of-three) as the pivot and use a Hoare-style partition that walks inward from both ends. The intermediate states come out different, but the unchanging rule is the same: at the end of the partition the pivot is in place, smaller on its left, larger on its right. On the exam, read which scheme is asked for.

The worst case

If the pivot is the largest (or smallest) element every time, the split is “n − 1 and 0”. Giving a sorted array to quick sort with the last element as pivot does exactly this:

partition [0..5] pivot 6 at 5 -> [1, 2, 3, 4, 5, 6]
partition [0..4] pivot 5 at 4 -> [1, 2, 3, 4, 5, 6]
partition [0..3] pivot 4 at 3 -> [1, 2, 3, 4, 5, 6]
partition [0..2] pivot 3 at 2 -> [1, 2, 3, 4, 5, 6]
partition [0..1] pivot 2 at 1 -> [1, 2, 3, 4, 5, 6]
comps=15

$T(n) = T(n-1) + n$ → O(n²). 499 500, 1 999 000, 7 998 000 comparisons for n = 1000, 2000, 4000: exactly n(n−1)/2. The fix: choose the pivot at random or take the median of the first, middle and last elements. In the average case the splits are balanced and O(n log n) is obtained.

Heap sort (overview)

A max-heap is a complete binary tree stored in an array in which every node is greater than or equal to its children. In the array, the children of index i are 2i + 1 and 2i + 2, and its parent is (i − 1) / 2. The largest element is always at the root (index 0).

Heap sort has two phases:

1. Build the heap. Starting from the last internal node (index n/2 − 1) and going toward the root, sift each node down: if the node is smaller than its larger child, swap, and continue. O(n) in total.
2. Extract. Swap the root (the largest) with the end of the array, shrink the heap by one, and sift the new root down. Repeat n − 1 times. Each sift is O(log n).

static void siftDown(int[] a, int i, int n) {
    while (2 * i + 1 < n) {
        int c = 2 * i + 1;                         // left child
        if (c + 1 < n && a[c + 1] > a[c]) c++;     // larger child
        if (a[i] >= a[c]) break;
        int t = a[i]; a[i] = a[c]; a[c] = t;
        i = c;
    }
}

static void heapSort(int[] a) {
    int n = a.length;
    for (int i = n / 2 - 1; i >= 0; i--) siftDown(a, i, n);
    for (int end = n - 1; end > 0; end--) {
        int t = a[0]; a[0] = a[end]; a[end] = t;
        siftDown(a, 0, end);
    }
}

{4, 10, 3, 5, 1}:

max-heap: [10, 5, 3, 4, 1]
extract 10 -> [5, 4, 3, 1, 10]
extract 5 -> [4, 1, 3, 5, 10]
extract 4 -> [3, 1, 4, 5, 10]
extract 3 -> [1, 3, 4, 5, 10]

Always O(n log n), O(1) extra memory. But it is unstable, and because it is not cache friendly it is slower than quick sort in practice. The details of the heap structure are in SEN2212.

Measurement: n log n

Number of comparisons on random arrays:

n=10000 merge comps=120464 quick comps=154970  n*log2(n)=132877
n=20000 merge comps=260792 quick comps=342401  n*log2(n)=285754
n=40000 merge comps=561703 quick comps=701837  n*log2(n)=611508
n=80000 merge comps=1203361 quick comps=1545944  n*log2(n)=1303017

Both are of the same magnitude as n log₂ n and grow about 2.1-2.2 times when n doubles (it would be 4 if quadratic). Even though quick sort makes more comparisons, it is usually faster in practice: no auxiliary array, no copying.

All the sorts: a comparison table

A stability test: applying a single Lomuto partition to records with keys (2a, 2b, 1)

after one Lomuto partition: [1, 2b, 2a]

While pivot 1 was swapped to the front, 2a was thrown to the end. Merge sort gives 1 2a 2b on the same input.

Common mistakes

merge [38] + [27] -> [27, 38]
merge [43] + [3] -> [3, 43]
merge [27, 38] + [3, 43] -> [3, 27, 38, 43]
merge [9] + [82] -> [9, 82]
merge [9, 82] + [10] -> [9, 10, 82]
merge [3, 27, 38, 43] + [9, 10, 82] -> [3, 9, 10, 27, 38, 43, 82]

j=0  7 >= 5 skip       [7, 2, 9, 4, 3, 8, 5]
j=1  2 < 5, i=0 swap   [2, 7, 9, 4, 3, 8, 5]
j=2  9 skip
j=3  4 < 5, i=1 swap   [2, 4, 9, 7, 3, 8, 5]
j=4  3 < 5, i=2 swap   [2, 4, 3, 7, 9, 8, 5]
j=5  8 skip
put the pivot at i+1 = 3  [2, 4, 3, 5, 9, 8, 7]

partition [0..6] pivot 5 at 3 -> [2, 4, 3, 5, 9, 8, 7]
partition [0..2] pivot 3 at 1 -> [2, 3, 4, 5, 9, 8, 7]
partition [4..6] pivot 7 at 4 -> [2, 3, 4, 5, 7, 8, 9]
partition [5..6] pivot 9 at 6 -> [2, 3, 4, 5, 7, 8, 9]

static void merge(int[] a, int[] tmp, int lo, int mid, int hi) {
    int i = lo, j = mid + 1, k = lo;
    while (i <= mid && j <= hi) {
        if (a[i] <= a[j]) tmp[k++] = a[i++];   // <= for stability
        else              tmp[k++] = a[j++];
    }
    while (i <= mid) tmp[k++] = a[i++];          // leftover left
    while (j <= hi)  tmp[k++] = a[j++];          // leftover right
    for (k = lo; k <= hi; k++) a[k] = tmp[k];    // copy back
}

static void mergeSort(int[] a, int[] tmp, int lo, int hi) {
    if (lo >= hi) return;
    int mid = (lo + hi) / 2;
    mergeSort(a, tmp, lo, mid);
    mergeSort(a, tmp, mid + 1, hi);
    merge(a, tmp, lo, mid, hi);
}

static int partition(int[] a, int lo, int hi) {
    int pivot = a[hi];
    int i = lo - 1;
    for (int j = lo; j < hi; j++) {
        if (a[j] < pivot) {
            i++;
            int t = a[i]; a[i] = a[j]; a[j] = t;
        }
    }
    int t = a[i + 1]; a[i + 1] = a[hi]; a[hi] = t;
    return i + 1;
}

static void quickSort(int[] a, int lo, int hi) {
    if (lo >= hi) return;
    int p = partition(a, lo, hi);
    quickSort(a, lo, p - 1);    // EXCLUDING the pivot
    quickSort(a, p + 1, hi);
}