Sorting 2: merge sort and quicksort

Sorting a million values by comparing every pair takes about 500 billion comparisons; merge sort needs about 20 million.

Split the problem, solve the halves

The methods in the last unit work on the whole list at once and pay for it with about n² comparisons. The two methods in this unit use a different plan, called divide and conquer. Split the list into smaller parts, sort each part with the same method, and then combine the sorted parts. The splitting continues until a part has one value or none, and a list of one value is already sorted. Because the method calls itself on smaller lists, it is recursive (unit 6 looks at recursion in detail).

Merge sort: the work is in the merging

Merge sort cuts the list in half, sorts the left half, sorts the right half, and merges the two sorted halves into one. The clever part is the merge. Two sorted lists can be combined by looking only at their front values. Compare the two fronts, write down the smaller one, and move past it. Repeat until one list is empty, then copy what is left of the other. Merging [1, 4, 7] and [2, 3, 8] goes 1 (1 vs 2), 2 (4 vs 2), 3 (4 vs 3), 4 (4 vs 8), 7 (7 vs 8), and then 8 is copied: 5 comparisons for 6 values. A merge of two lists with n values in total never needs more than n − 1 comparisons.

function merge(left, right) {
  const out = [];
  let i = 0, j = 0;
  while (i < left.length && j < right.length) {
    if (right[j] < left[i]) out.push(right[j++]);
    else out.push(left[i++]);
  }
  return out.concat(left.slice(i), right.slice(j));
}

function mergeSort(a) {
  if (a.length <= 1) return a;          // already sorted
  const mid = Math.floor(a.length / 2);
  return merge(mergeSort(a.slice(0, mid)), mergeSort(a.slice(mid)));
}

Why is this fast? Picture the halving as levels. A list of 8 values splits into 2 lists of 4, then 4 lists of 2, then 8 lists of 1: three levels, because 8 can be halved 3 times. At each level, all the merges together touch each value once, so a level costs at most about n comparisons. With log₂ n levels the total is about n log₂ n. For a million values that is about 20 million comparisons, against about 500 billion for the pair-by-pair methods. Split as [38, 27, 43, 3] and [9, 82, 10], as in the lab, the list [38, 27, 43, 3, 9, 82, 10] takes 14 comparisons; the code above splits it 3 and 4 and takes 13.

The price is memory. Merging needs somewhere to write the output, so merge sort uses a second list as large as the input. Merge sort is also stable: values that compare equal keep their original order, because the merge takes from the left list when the fronts are equal. That matters when you sort a table by one column after another, for example by city and then by name.

Quicksort: split around a pivot

Quicksort divides the list in a different way. It picks one value, the pivot, and rearranges the list so that everything smaller than the pivot comes before it and everything else comes after it. This step is called partitioning. Now the pivot is in its final place, and the two sides can be sorted separately with the same method. Nothing needs merging afterwards, because every value on the left is already smaller than every value on the right.

The lab uses a common textbook version that takes the last value of each part as the pivot. On [5, 1, 4, 2, 8] the pivot 8 is compared with the four other values, all smaller, so 8 stays at the end. The next part [5, 1, 4, 2] uses pivot 2: only 1 is smaller, so after two swaps the list is [1, 2, 4, 5, 8]. One more comparison handles [4, 5]. Total: 8 comparisons and 2 swaps.

When the pivot lands near the middle, each split halves the problem and quicksort takes about n log₂ n comparisons, like merge sort. It also works inside the original list without a second copy. But a bad pivot hurts. If the list is already sorted and the pivot is always the last value, every split peels off just one value, and quicksort falls back to about n²/2 comparisons: 10 for [1, 2, 3, 4, 5], the same as selection sort. Real libraries avoid this by choosing the pivot more carefully, for example at random or as the middle of three sample values.