The median of three strategy is used to speed up the the quick sort algorithm. I wrote an article about quick sort before, if you don't familiar with the quick sort algorithm, check the article first.

The quick sort algorithm is a divide and conquer algorithm. Specifically, we choose a pivot, then move element to make left part lower than pivot, and right part bigger than pivot. So for one loop, we split the array into 2 half.

The key here is that how we split the array. In previous article, we just use a simple approach, select the last element of the array and use it as the pivot the split the array. In that case, we assume the array is random, so the time complexity is O(nlog(n)) in average. But if the array is sorted, then when we select the last element as pivot, we can't split the array into 2 half because this pivot is the max or min value. So in this case, the time complexity becomes O(n^2).

The median of three strategy is a technique to make the pivot selection part more smart. Specifically, for every iteration, we will choose 3 values as candidates for pivot. We calculate the median of the 3 values, then choose it as the pivot.

The code is very simple to implement. In typical quick sort partition function, we choose the last element directly.

function partition(nums: number[], low: number, high: number): number {
    let pivot = nums[high];
    let p = low;
    for (let i = low; i < high; i++) {
        if (nums[i] <= pivot) {
            [nums[i], nums[p]] = [nums[p], nums[i]];
            p += 1;
        }
    }
    [nums[high], nums[p]] = [nums[p], nums[high]];
    return p;
}

By using the median of three, we will compare low and mid element, and choose the median one.

function partition(nums: number[], low: number, high: number): number {
    const mid = low + Math.floor((high - low) / 2);
    if (
        (nums[low] > nums[mid] && nums[low] < nums[high]) ||
        (nums[low] < nums[mid] && nums[low] > nums[high])
    ) {
        [nums[low], nums[high]] = [nums[high], nums[low]];
    } else if (
        (nums[mid] > nums[low] && nums[mid] < nums[high]) ||
        (nums[mid] < nums[low] && nums[mid] > nums[high])
    ) {
        [nums[mid], nums[high]] = [nums[high], nums[mid]];
    }

    // the same as above
}

Note that if the median value is not the high value, we can simple swap the median value with the high value, so the other part remains the same.

As you can see, in this way, we can limit the number of worse cases.

To calculate the median value, we can use xor to speed up the operations. For example, if the low value is the median value, then +(nums[low] > nums[mid]) and +(nums[low] > nums[high]) should one has value 1, the other has value 0, then we use xor to make it 1. Same thing goes with the mid value.

function partition(nums: number[], low: number, high: number): number {
    const mid = low + Math.floor((high - low) / 2);
    if ((+(nums[low] > nums[mid])) ^ (+(nums[low] > nums[high]))) {
        [nums[low], nums[high]] = [nums[high], nums[low]];
    } else if ((+(nums[mid] < nums[low])) ^ (+(nums[mid] < nums[high]))) {
        [nums[mid], nums[high]] = [nums[high], nums[mid]];
    }

    // the same as above
}