Quick Sort

Quicksort is the most widely used comparison sort in practice. Its average-case O(n log n) comes with a very small constant factor because the partitioning step works entirely in-place with excellent cache locality. The algorithm was invented by Tony Hoare in 1959 and remains the basis of most standard-library sorts (often combined with insertion sort for small sub-arrays, as in introsort).

The Partition Step

Choose a pivot element. Rearrange the array so every element smaller than the pivot ends up to its left and every element larger ends up to its right. The pivot is now in its final sorted position. Recursively apply the same process to the left and right sub-arrays.

Lomuto Partition Scheme

The Lomuto scheme always picks the last element as the pivot and maintains an index i pointing to the boundary between the “less-than” region and the “not-yet-processed” region.

function partition(arr, low, high) {
  const pivot = arr[high]; // last element as pivot
  let i = low - 1;         // boundary of "less-than" region

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

  // Place pivot in its final position
  [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];
  return i + 1; // pivot index
}

function quickSort(arr, low = 0, high = arr.length - 1) {
  if (low < high) {
    const pivotIndex = partition(arr, low, high);
    quickSort(arr, low, pivotIndex - 1);
    quickSort(arr, pivotIndex + 1, high);
  }
  return arr;
}

console.log(quickSort([10, 7, 8, 9, 1, 5]));
// => [1, 5, 7, 8, 9, 10]

Randomised Pivot

The classic weakness of quicksort is its O(n²) worst case, triggered by already-sorted (or reverse-sorted) input when the last element is always chosen as the pivot — every partition produces an empty left side and an (n - 1)-element right side, leading to n levels of recursion instead of log n.

The fix is to swap a randomly chosen element into the pivot position before partitioning:

function randomPartition(arr, low, high) {
  const r = low + Math.floor(Math.random() * (high - low + 1));
  [arr[r], arr[high]] = [arr[high], arr[r]];
  return partition(arr, low, high);
}

With a random pivot, the probability of consistently bad splits on any fixed input is astronomically small. The expected time remains O(n log n).

Stability

Quicksort is not stable. The partition step can move a later element across an earlier equal element. If stability is required, use merge sort or TimSort.

Complexity

The O(log n) space is the recursion stack depth in the average case; the worst case pushes this to O(n).

Hoare vs Lomuto

The Hoare partition scheme (two pointers walking toward each other) does roughly three times fewer swaps than Lomuto on average and handles duplicates more evenly. Lomuto is simpler to implement correctly and easier to reason about, which is why it appears in most textbooks.

Up Next

Heap sort achieves O(n log n) in all cases and uses O(1) space — the price is poor cache locality and lack of stability.