Quick Sort

Explanation

Quick sort's key operation is partitioning: pick a pivot, rearrange the array so all elements less than the pivot come before it and all greater elements come after it, then recursively sort both partitions. The pivot ends up in its final sorted position after partitioning. Unlike merge sort, quick sort is in-place — it rearranges elements in the original array without auxiliary storage. The choice of pivot determines performance. With a good pivot (ideally the median), each partition splits the array roughly in half, giving O(log n) recursive depth and O(n log n) total. With a bad pivot (always the min or max — what happens with sorted input if you pick the first element as pivot), one partition is size 0 and the other is n-1, giving O(n) depth and O(n²) total. Randomized quick sort (pick a random pivot) makes worst-case O(n²) astronomically unlikely in practice. The Lomuto partition scheme (easy to understand) and Hoare partition scheme (original, slightly more efficient) are the two standard partitioning approaches. C's qsort, C++'s std::sort (actually introsort — quick sort with heap sort fallback), and many other standard libraries use quick sort variants. In practice, quick sort is often faster than merge sort for in-memory sorting despite the same average O(n log n) — better cache locality (in-place) and smaller constants. For nearly-sorted data, merge sort (or Timsort) wins. For random data, quick sort often wins.

Code Example

// Quick sort with randomized pivot
function quickSort(arr, lo = 0, hi = arr.length - 1) {
  if (lo >= hi) return;

  const pivotIdx = partition(arr, lo, hi);
  quickSort(arr, lo, pivotIdx - 1);
  quickSort(arr, pivotIdx + 1, hi);
}

function partition(arr, lo, hi) {
  // Randomize pivot to avoid O(n²) on sorted input
  const randIdx = lo + Math.floor(Math.random() * (hi - lo + 1));
  [arr[randIdx], arr[hi]] = [arr[hi], arr[randIdx]];
  
  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]];
  return i + 1;
}

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

Why It Matters for Engineers

Quick sort is the canonical example of in-place divide-and-conquer and appears in almost every algorithms course and interview curriculum. Understanding the partition step — one of the more subtle pointer-manipulation algorithms — builds the same skill used in two-pointer and sliding-window techniques. Quick sort also teaches the critical lesson about worst-case vs. average-case complexity: an algorithm can be O(n²) in the worst case and still be the fastest practical choice because the worst case is rare or avoidable. This nuance — "Big O isn't the whole story" — is important for real engineering decisions.