Writing a 'Median of Three' Pivot Helper for QuickSort

QuickSort Basics
The Pivot
Median Value
Update Array Around Pivot

QuickSort Basics

QuickSort is an algorithm for sorting an array based on a pivot point in the array. To see a 3 minute visual on how QuickSort works, check out this video.

To implement QuickSort (or skip ahead to the pivot if you prefer):

• Choose a pivot from the array (more how to choose a pivot below)
• The pivot function should also update the array in place by moving
  • all elements smaller than the pivot value to the left of the pivot and
  • all elements greater than (or equal to) the pivot to its right.
• Once the elements on either side of the pivot are on their correct side, the pivot value itself is correctly placed into its final location in the sorted array.
• Since the pivot value is now correct, you can disregard it and move on to sorting the elements on either side of it:
  • Do this by recursively calling QuickSort again on both the left side of the pivot and the right side of the pivot.

The code for the outer QuickSort function might look something like this:

function numberCompare(a, b) {
    return a - b;
}

function quickSort(arr, comparator = numberCompare, start = 0, end = arr.length - 1) {

    if (start < end) {
        const iPivot = pivot(arr, comparator, start, end); 

        quickSort(arr, comparator, start, iPivot - 1);
        quickSort(arr, comparator, iPivot + 1, end);
    }

    return arr;
}

Some code notes:
numberCompare(): We provide a default comparator function (numberCompare) for sorting numbers in ascending order. To sort the array differently (perhaps alphabetically for strings, or in descending order), supply a different comparator function when invoking quickSort.

pivot(): This helper function will handle the following steps:

• select a value from the array as the pivot
• mutate the array in place so values less than the pivot are moved to its left and values greater than/equal to the pivot are moved to its right
• return the index of the pivot value's final location (after array mutation is complete), allowing quickSort to be called again on each side of the pivot index

The Pivot

With the QuickSort basics out of the way, let's talk about the pivot. Technically, you can choose any value in the array as the pivot. However, some options can result in less optimal runtimes.

Naive Options:

1. Always choose the first element of the current array subsection.
2. Always choose the last element of the current array subsection.

Both of these will work and can be a bit simpler to implement. However, they run the risk of worse time complexity. On a sorted or nearly sorted array, these will both have O(n^2) runtime as each iteration of sorting will have to sort all of the remaining elements.

Pivot Improvements:

1. Random value from the array as pivot
2. Median Value of the array

These options can improve the runtime and increase the likelihood of an O(n log n) runtime, including for sorted arrays. We'll discuss using a median value.

Median Value

Median refers to the middle value in a sorted set of data, with an equal number of items on either side of it. Ideally, every time we run QuickSort, we want to pivot around the median value of our current array subsection, rather than skewing the implementation towards the highest or lowest values.

Unfortunately, we don't actually know the median value because the array is not yet sorted. Instead we can use the "Median of Three" Strategy.

Median of Three

To implement the "Median of Three" strategy, select the first, last, and middle elements from your current array (or array portion as the recursive calls begin). Take the median (middle) value of those three elements to use for the current pivot.

The code to find the median might look something like:

function bigger(arr, a, b) {
  if (arr[a] > arr[b]) return a;
  return b;
}

function getMedianPivotIdx(arr, start = 0, end = arr.length - 1) {
  const mid = Math.floor((start + end) / 2);

  const iBiggest = bigger(arr, start, bigger(arr, mid, end));

  if (iBiggest === start) return bigger(arr, mid, end);

  if (iBiggest === end) return bigger(arr, start, mid);

  return bigger(arr, start, end);
}

This function will return the index of the median value between the start, end, middle values, allowing you to use that for a pivot.

Update Array Around Pivot

With the pivot selected, implement the rest of the pivot function:

• find the correct location for the pivot by moving
  • all values less than the pivot value to its left and
  • all values greater than (or equal to) the pivot to its right.

One important implementation detail when actually writing this pivot code is to make sure you move the pivot value out of the way before comparing the rest of the values. (In the code below, you'll see we swap the pivot and the end values before iterating through the array to move elements to their proper side of the pivot.)

The full pivot helper might look like:

function swap(arr, idxA, idxB) {
  [arr[idxA], arr[idxB]] = [arr[idxB], arr[idxA]];
}

function pivot(
  arr,
  comparator = numberCompare,
  start = 0,
  end = arr.length - 1
) {
  const iPivotStart = getMedianPivotIdx(arr, start, end);
  const pivotVal = arr[iPivotStart];
  let iPivotTarget = start;

  swap(arr, iPivotStart, end); //swap the end and the pivot before iterating through array to update elements in place
  const iPivotTemp = end;

  for (let i = start; i < iPivotTemp; i++) { //update array in place by moving smaller elements to the front of the array
    const curr = arr[i];

    if (comparator(curr, pivotVal) < 0) {
      swap(arr, i, iPivotTarget);
      iPivotTarget++; // iPivotTarget is incremented with each swap to provide the correct location for the current swap and count the number of swaps. The final pivot index should be equal to the number of swaps.
    }
  }

  swap(arr, iPivotTemp, iPivotTarget); // after moving all smaller elements to the front of the array, swap the pivot with the first element that is larger than the pivot
  return iPivotTarget; // return the final index of the pivot
}