Counting / Radix

// ===== Idea =====
// Sort by sorting one DIGIT at a time, from least significant (LSD) to most significant.
// Each pass uses a STABLE sort (counting sort).
// Total time: O(d * (n + k)) where d = digits, k = base.
// For 32-bit ints: ~4 passes with base 256.

// ===== LSD radix sort (integers) =====
function radixSortLSD(arr) {
  if (arr.length === 0) return arr;
  let max = Math.max(...arr);
  let exp = 1;
  while (Math.floor(max / exp) > 0) {
    arr = countingSortByDigit(arr, exp);
    exp *= 10;
  }
  return arr;
}

function countingSortByDigit(arr, exp) {
  const n = arr.length;
  const output = new Array(n);
  const count = new Array(10).fill(0);
  for (let i = 0; i < n; i++) count[Math.floor(arr[i] / exp) % 10]++;
  for (let i = 1; i < 10; i++) count[i] += count[i - 1];
  for (let i = n - 1; i >= 0; i--) {
    const d = Math.floor(arr[i] / exp) % 10;
    output[count[d] - 1] = arr[i];
    count[d]--;
  }
  return output;
}

console.log(radixSortLSD([170, 45, 75, 90, 802, 24, 2, 66]));
// [2, 24, 45, 66, 75, 90, 170, 802]

// ===== When radix wins =====
// - Bounded integer keys (32-bit, 64-bit fit easily)
// - Large datasets where O(n log n) overhead dominates
// - Cache-friendly streaming workloads

// External examples: GPU sorts, sorting billions of records on disk.

// ===== MSD radix (recursive, more complex) =====
// Useful for strings (sort by first character into buckets, recurse on each bucket).
// Used in implementations like Cilk Sort, parallel sorts.

// ===== Stability =====
// LSD radix MUST use a stable inner sort.
// Counting sort is stable; quicksort is not.

// ===== Negative integers =====
// Standard LSD only handles non-negative. Trick: separate negative + positive arrays, sort
// each, then concatenate (negative descending becomes ascending after sign flip).

// ===== Floats =====
// IEEE 754 has the same byte order as signed integers when reinterpreted... almost.
// Approach: reinterpret as int, flip the sign bit for positives, flip all bits for negatives,
// radix-sort as unsigned, undo the flip. Works perfectly, but tricky.

// ===== Strings =====
// MSD radix: process leftmost character first.
// O(d * n) where d = max string length, n = number of strings.
// Combined with quicksort hybrid for very long strings.

// ===== Comparison with quicksort =====
// QuickSort:   O(n log n) average, in place, cache-friendly, general purpose.
// Radix:       O(n) for bounded keys, NOT in place (uses extra memory), wins on huge n.
// TimSort:     O(n log n), stable, used in JS / Python sort. Best general-purpose default.

// ===== Patterns to internalise =====
// - Use built-in sort by default; radix when n is huge + keys bounded
// - Stable counting sort as the inner pass
// - Profile before optimising
// - Cache-friendly implementations matter on very large data

// ===== Pitfalls =====
// - Negative integers without sign handling
// - Forgetting the stable inner sort requirement
// - Extra memory cost on memory-constrained systems
// - Float / string radix correctness is fiddly; use a tested library

// Counting / radix beat O(n log n) when keys have bounded range.
// Great for fixed-width ints, IPv4 addresses, fixed-length strings.