QuickSort: The Clever Sorting Algorithm

Sorting data is a common task in programming, and I’ve learned that QuickSort is one of the most efficient ways to do it. I’ve recently been learning about this algorithm. What makes it so efficient, when to use it, and if it is practical.

What QuickSort Does

QuickSort takes an unordered list like [5, 2, 8, 1], and sorts it into order, like [1, 2, 5, 8]. It’s a “divide and conquer” method:

1. It picks a “pivot” (say, the first number, which is 5).
2. Split the list: numbers smaller than the pivot go left, bigger ones go right.
3. Repeat on each half until everything’s sorted.

Here’s a simple JavaScript version

/**
 * Sorts an array in ascending order using the quicksort algorithm.
 * The function modifies the input array in-place and uses an optimized
 * approach by sorting the smaller partition first to reduce stack space.
 *
 * @param {Array<number>} arr - The array to be sorted
 * @param {number} [low=0] - The starting index of the partition to sort
 * @param {number} [high=arr.length-1] - The ending index of the partition to sort
 * @returns {Array<number>} The sorted array
 */
function quickSort(arr, low = 0, high = arr.length - 1) {
    while (low < high) {
        const pivotIndex = partition(arr, low, high);
        // Sort the smaller partition first to optimize stack space
        if (pivotIndex - low < high - pivotIndex) {
            quickSort(arr, low, pivotIndex);
            low = pivotIndex + 1;
        } else {
            quickSort(arr, pivotIndex + 1, high);
            high = pivotIndex;
        }
    }
    return arr;
}

/**
 * Partitions an array around a pivot element for the quicksort algorithm.
 * Uses the first element as the pivot and rearranges elements so that all
 * values less than the pivot are on the left and all values greater are on
 * the right.
 *
 * @param {Array<number>} arr - The array to partition
 * @param {number} low - The starting index of the partition
 * @param {number} high - The ending index of the partition
 * @returns {number} The final position of the pivot element
 */
function partition(arr, low, high) {
    const pivot = arr[low];
    let i = low - 1;
    let j = high + 1;
    while (true) {
        do { i++; } while (arr[i] < pivot);
        do { j--; } while (arr[j] > pivot);
        if (i >= j) return j;
        [arr[i], arr[j]] = [arr[j], arr[i]];
    }
}

JavaScript

It picks 5, moves 2 and 1 left, 8 right, then sorts each side. Done.

How It Performs

QuickSort is known for being fast, especially for most lists you throw at it. It sorts in-place, reusing the original list without needing extra space, which keeps memory use low. While it can slow down with really big or tricky lists, it’s usually quick and efficient for most things.

QuickSort vs Native Implementations

My exploration of QuickSort implementations in PHP and JavaScript reveals a clear performance gap compared to native sorting solutions. In PHP, benchmarks showed native sort() sorted an array of 10,000 items 85% faster (8.1ms vs 1.2ms) than our PHP implementation. JavaScript followed a similar trend, with Array.sort() sorting an array of 500 items 68% faster (1.9ms vs 0.6ms) than our JavaScript implementation.

My Thoughts

Is writing a custom QuickSort worth it? It seems generally, no – if speed is the priority, native functions appear unbeatable. However, implementing QuickSort offers educational value and flexibility for specific use cases. For production code, stick with the native solution unless you have a compelling reason to roll your own.

Code by Tom