Quick sort

Pick a pivot, put smaller items left and larger right, then sort each side. Fast in practice, in place.

How it works

Partition: walk the range and swap anything smaller than the pivot to the front. Put the pivot right after them; it's now in its final position. Recurse on both sides. A good pivot splits evenly (n log n). A bad one, like always the first item on sorted input, gives O(n²). Middle or random pivots avoid that.

Reach for it when

• In-memory sort where memory matters
• Quickselect: find the kth smallest in O(n) average

Copyfunction quickSort(a, lo = 0, hi = a.length - 1) {
  if (lo >= hi) return a;
  const mid = lo + ((hi - lo) >> 1);
  [a[mid], a[hi]] = [a[hi], a[mid]]; // middle pivot dodges sorted-input worst case
  const pivot = a[hi];
  let i = lo; // everything left of i is < pivot
  for (let j = lo; j < hi; j++)
    if (a[j] < pivot) {
      [a[i], a[j]] = [a[j], a[i]];
      i++;
    }
  [a[i], a[hi]] = [a[hi], a[i]]; // pivot lands in its final spot
  quickSort(a, lo, i - 1);
  quickSort(a, i + 1, hi);
  return a;
}

Traps

• Always picking the first or last pivot on sorted input is O(n²).
• Many duplicates hurt basic partitioning (three-way partition fixes it).