Quick Sort Algorithm

Pick an element (the pivot). Move everything smaller to the left, everything larger to the right. Now the pivot is in its final position. Recurse on both sides.

That's quick sort. It's the default sorting algorithm in most standard libraries for a reason — fast in practice, low overhead, sorts in place.

The intuition

Imagine organizing a shelf of books by height. Pick one book. Put shorter books to the left, taller ones to the right. That book is now in the right spot. Repeat for each side.

The code

function quickSort(arr, left = 0, right = arr.length - 1) {
    if (left >= right) return arr;

    const pivotIndex = partition(arr, left, right);
    quickSort(arr, left, pivotIndex - 1);
    quickSort(arr, pivotIndex + 1, right);

    return arr;
}

function partition(arr, left, right) {
    const pivot = arr[right];
    let i = left;

    for (let j = left; j < right; j++) {
        if (arr[j] < pivot) {
            [arr[i], arr[j]] = [arr[j], arr[i]];
            i++;
        }
    }

    [arr[i], arr[right]] = [arr[right], arr[i]];
    return i;
}

quickSort([3, 6, 8, 1, 5, 9, 2, 7, 4]);
// [1, 2, 3, 4, 5, 6, 7, 8, 9]

Complexity

• Time: O(n log n) average. O(n^2) worst case — when the pivot is always the smallest or largest element (already sorted input with last-element pivot).
• Space: O(log n) average for the recursion stack. O(n) worst case.

Trade-offs

Quick sort is faster than merge sort in practice due to better cache locality and no extra array allocation. But it's not stable — equal elements might get reordered. And the O(n^2) worst case is real.

Mitigation strategies: randomize the pivot choice, use median-of-three, or switch to insertion sort for small subarrays. Most production implementations (like V8's Array.sort) use Timsort — a hybrid of merge sort and insertion sort that guarantees O(n log n) and stability.