Sorting is foundational. The right choice depends on data size, distribution, memory constraints, and stability requirements. This edition covers quicksort, mergesort, heapsort, and linear-time sorts: radix, counting, and bucket.

Idea: Partition around a pivot so left < pivot < right, then recurse.

• Time: average O(n log n), worst O(n²) with bad pivots
• Space: O(log n) stack average (in-place partition)
• Stability: Not stable (unless extra handling)

function quicksort(a, l = 0, r = a.length - 1) {
  while (l < r) {
    const p = partition(a, l, r); // Lomuto/Hoare
    if (p - l < r - p) { // tail call elimination
      quicksort(a, l, p - 1);
      l = p + 1;
    } else {
      quicksort(a, p + 1, r);
      r = p - 1;
    }
  }
}

function partition(a, l, r) {
  const m = l + ((r - l) >> 1);
  const pivot = medianOf3(a[l], a[m], a[r]);
  // Hoare partition example
  let i = l - 1, j = r + 1;
  while (true) {
    do { i++; } while (a[i] < pivot);
    do { j--; } while (a[j] > pivot);
    if (i >= j) return j;
    [a[i], a[j]] = [a[j], a[i]];
  }
}

Idea: Divide array, sort halves, merge in linear time.

• Time: O(n log n) worst-case
• Space: O(n) auxiliary for straightforward implementation
• Stability: Stable

function mergesort(a) {
  if (a.length <= 1) return a;
  const mid = a.length >> 1;
  return merge(mergesort(a.slice(0, mid)), mergesort(a.slice(mid)));
}

function merge(L, R) {
  const out = [];
  let i = 0, j = 0;
  while (i < L.length && j < R.length) {
    if (L[i] <= R[j]) out.push(L[i++]);
    else out.push(R[j++]);
  }
  return out.concat(L.slice(i)).concat(R.slice(j));
}

Idea: Build a max-heap, then repeatedly extract max to end.

• Time: O(n) build + O(n log n) extraction
• Space: O(1) extra, in-place
• Stability: Not stable

function heapsort(a) {
  const n = a.length;
  for (let i = (n >> 1) - 1; i >= 0; i--) siftDown(a, i, n);
  for (let end = n - 1; end > 0; end--) {
    [a[0], a[end]] = [a[end], a[0]];
    siftDown(a, 0, end);
  }
}

function siftDown(a, i, n) {
  while (true) {
    let l = (i << 1) + 1, r = l + 1, m = i;
    if (l < n && a[l] > a[m]) m = l;
    if (r < n && a[r] > a[m]) m = r;
    if (m === i) return;
    [a[i], a[m]] = [a[m], a[i]];
    i = m;
  }
}

These beat comparison sorts under the right constraints.

Counting Sort

• Assumes: Integers in known small range [0, k]
• Time: O(n + k), Space: O(n + k), Stable: Yes (if implemented via prefix sums)

function countingSort(a, k) {
  const c = new Array(k + 1).fill(0), out = new Array(a.length);
  for (const x of a) c[x]++;
  for (let i = 1; i <= k; i++) c[i] += c[i - 1];
  for (let i = a.length - 1; i >= 0; i--) out[--c[a[i]]] = a[i];
  return out;
}

Radix Sort

• Assumes: Fixed-width keys (e.g., 32-bit ints, strings of bounded length)
• Time: O(d·(n + b)) for d digits and base b; typically stable (using stable bucket per digit)

Bucket Sort

• Assumes: Uniform distribution over [0, 1)
• Time: Average O(n) with n buckets; sort each bucket with insertion sort

• Quicksort: Avg O(n log n), worst O(n²), in-place, not stable, cache-friendly
• Mergesort: O(n log n) worst, stable, O(n) extra memory (classic)
• Heapsort: O(n log n) worst, in-place, not stable, poorer constants
• Counting: O(n + k), stable, needs range k
• Radix: O(d·(n + b)), stable, needs fixed-width keys
• Bucket: Avg O(n) under uniform distribution