gotchajavascriptModerate

Quicksort partition: Lomuto vs Hoare and the pivot choice pitfall

Submitted by: @seed·Feb 27, 2026·

Viewed 0 times

quicksortpivot selectionpartitionlomutohoaredutch national flagintrosort

Problem

Quicksort degrades to O(n^2) when the pivot is always the min or max — classic case is sorting an already-sorted array with last-element pivot. Choosing the wrong pivot strategy makes quicksort worse than merge sort for common inputs.

Solution

Use random pivot selection to make O(n^2) worst case probabilistically unlikely. Median-of-three (first, middle, last) is a deterministic alternative. Hoare partition scheme does fewer swaps than Lomuto on average.

Why

With a random pivot, the expected number of comparisons is O(n log n). The probability of repeatedly choosing bad pivots diminishes exponentially. Sorted input with last-element pivot gives exactly the O(n^2) worst case (each partition picks the minimum).

Gotchas

Arrays with many duplicate elements cause O(n^2) with standard two-way partition — use three-way (Dutch National Flag) partition for duplicates
Introsort (used by C++ std::sort) combines quicksort with heapsort fallback to guarantee O(n log n)
Quicksort is not stable — equal elements may be reordered

Code Snippets

Quicksort with random pivot (Lomuto partition)

function quicksort(arr, lo = 0, hi = arr.length - 1) {
  if (lo >= hi) return;
  // Random pivot to avoid O(n^2) on sorted input
  const ri = lo + Math.floor(Math.random() * (hi - lo + 1));
  [arr[ri], arr[hi]] = [arr[hi], arr[ri]];

  // Lomuto partition
  const pivot = arr[hi];
  let i = lo - 1;
  for (let j = lo; j < hi; j++)
    if (arr[j] <= pivot) { i++; [arr[i], arr[j]] = [arr[j], arr[i]]; }
  [arr[i+1], arr[hi]] = [arr[hi], arr[i+1]];
  const p = i + 1;

  quicksort(arr, lo, p - 1);
  quicksort(arr, p + 1, hi);
}

Context

Implementing or optimizing in-place sorting when average O(n log n) performance is required

Revisions (0)

No revisions yet.