Counting, Radix & Bucket Sort

The O(n log n) lower bound for sorting is a fact about comparison sorts — algorithms that determine order only by asking "is a greater than b?" Non-comparison sorts exploit additional information about the elements themselves (their values, their digits, their distribution) to sort faster than O(n log n) in special cases.

These three algorithms are the most important non-comparison sorts. Each is O(n) under its specific assumptions — and those assumptions come up often enough in real problems that every competitive programmer and interview candidate should know them.

Counting Sort

Counting sort works for integers in a known range [0, k]. Instead of comparing elements, it counts how many times each value appears, then reconstructs the sorted array from the counts.

Time: O(n + k). Space: O(k) for the count array. When k = O(n), this is O(n) — a genuine improvement over O(n log n). When k >> n (e.g., 32-bit integers), it is worse than comparison sorts.

// Counting sort for non-negative integers in range [0, k]
function countingSort(arr, k) {
  // k = maximum value in arr (or known upper bound)

  // Step 1: Count occurrences of each value
  const count = new Array(k + 1).fill(0);
  for (const num of arr) {
    count[num]++;
  }
  // count[i] = number of times i appears in arr

  // Step 2: Reconstruct sorted array
  const sorted = [];
  for (let i = 0; i <= k; i++) {
    for (let j = 0; j < count[i]; j++) {
      sorted.push(i);
    }
  }
  return sorted;
}

countingSort([4, 2, 2, 8, 3, 3, 1], 8);
// count = [0, 1, 2, 2, 1, 0, 0, 0, 1]
// → [1, 2, 2, 3, 3, 4, 8]

countingSort([4,2,2,8,3,3,1], 8) → [1,2,2,3,3,4,8]

The version above loses stability. For sorting objects by a key (where equal keys should maintain original order), use the prefix sum version:

// Stable counting sort — preserves relative order of equal elements
function countingSortStable(arr, k) {
  const n = arr.length;
  const count = new Array(k + 1).fill(0);

  // Count occurrences
  for (const num of arr) count[num]++;

  // Prefix sums: count[i] = number of elements <= i = starting position for i
  for (let i = 1; i <= k; i++) count[i] += count[i - 1];

  // Build output array scanning from RIGHT to LEFT (ensures stability)
  const output = new Array(n);
  for (let i = n - 1; i >= 0; i--) {
    output[count[arr[i]] - 1] = arr[i];
    count[arr[i]]--;
  }
  return output;
}

// Counting sort for negative integers (offset by min value)
function countingSortGeneral(arr) {
  if (arr.length === 0) return arr;
  const min = Math.min(...arr);
  const max = Math.max(...arr);
  const k = max - min;
  const count = new Array(k + 1).fill(0);
  for (const num of arr) count[num - min]++;
  const sorted = [];
  for (let i = 0; i <= k; i++) {
    for (let j = 0; j < count[i]; j++) sorted.push(i + min);
  }
  return sorted;
}

When Counting Sort Beats Everything

Sorting exam scores (0–100): k=100, O(n) regardless of n
Sorting ages (0–150): k=150, trivially O(n)
Sorting characters in a string (a-z): k=26, used in radix sort
Sorting months (1–12) or days (0–6): k=12 or 7
LeetCode 75 (Sort Colors): sort 0s, 1s, 2s — counting sort is O(n) with k=2

Radix Sort

Radix sort extends counting sort to multi-digit integers. Instead of sorting by the full value (which could require k up to 2^32 for 32-bit integers), it sorts one digit at a time using counting sort as a subroutine.

LSD (Least Significant Digit): sort by rightmost digit first, then second-to-last, ..., leftmost last. MSD (Most Significant Digit): sort by leftmost digit first, then recursively sort each bucket.

LSD is more common for fixed-length integers. MSD is better for variable-length strings.

// LSD Radix Sort for non-negative integers
function radixSortLSD(arr) {
  if (arr.length === 0) return arr;
  const max = Math.max(...arr);

  // Sort by each digit position from least significant to most significant
  for (let exp = 1; Math.floor(max / exp) > 0; exp *= 10) {
    arr = countingSortByDigit(arr, exp);
  }
  return arr;
}

// Stable sort by the digit at position 'exp' (1=ones, 10=tens, 100=hundreds, ...)
function countingSortByDigit(arr, exp) {
  const n = arr.length;
  const output = new Array(n);
  const count = new Array(10).fill(0);

  // Count occurrences of each digit (0–9)
  for (let i = 0; i < n; i++) {
    const digit = Math.floor(arr[i] / exp) % 10;
    count[digit]++;
  }

  // Prefix sums: count[d] = starting position for digit d in output
  for (let i = 1; i < 10; i++) count[i] += count[i - 1];

  // Build output (right to left for stability)
  for (let i = n - 1; i >= 0; i--) {
    const digit = Math.floor(arr[i] / exp) % 10;
    output[count[digit] - 1] = arr[i];
    count[digit]--;
  }
  return output;
}

radixSortLSD([170, 45, 75, 90, 802, 24, 2, 66]);
// Pass 1 (ones digit):  [170, 90, 802, 2, 24, 45, 75, 66]
// Pass 2 (tens digit):  [802, 2, 24, 45, 66, 170, 75, 90]
// Pass 3 (hundreds):    [2, 24, 45, 66, 75, 90, 170, 802]

radixSortLSD([170,45,75,90,802,24,2,66]) → [2,24,45,66,75,90,170,802]

Radix sort for strings (MSD):

// MSD Radix Sort for strings (sort by most significant character first)
function radixSortMSD(arr) {
  return msdSort(arr, 0);
}

function msdSort(arr, pos) {
  if (arr.length <= 1) return arr;

  // Group strings by character at position 'pos'
  const buckets = {};
  const finished = [];  // strings that ended at or before this position

  for (const str of arr) {
    if (pos >= str.length) {
      finished.push(str);
    } else {
      const ch = str[pos];
      if (!buckets[ch]) buckets[ch] = [];
      buckets[ch].push(str);
    }
  }

  // Recursively sort each bucket, then concatenate
  const sortedKeys = Object.keys(buckets).sort();
  const result = [...finished];
  for (const key of sortedKeys) {
    result.push(...msdSort(buckets[key], pos + 1));
  }
  return result;
}

radixSortMSD(['banana', 'apple', 'avocado', 'blueberry', 'apricot']);
// → ['apple', 'apricot', 'avocado', 'banana', 'blueberry']

Radix Sort Complexity

For n integers each with d digits in base b:

Time: O(d · (n + b)) — d passes of counting sort, each O(n + b)
Space: O(n + b) — output array + count array

For 32-bit integers with base 10: d = 10 digits, b = 10 → O(10 · (n + 10)) = O(n) For 32-bit integers with base 256: d = 4 bytes, b = 256 → O(4 · (n + 256)) = O(n) and 4x faster!

In practice, radix sort with base 256 (sorting byte by byte) often beats merge/quicksort for large arrays of integers — it genuinely is faster than O(n log n) in practice.

Bucket Sort

Bucket sort distributes elements into evenly-spaced buckets based on their value range, sorts each bucket (usually with insertion sort for small buckets), then concatenates.

Optimal when elements are uniformly distributed over a known range. Expected O(n) time, but degrades to O(n²) if all elements land in the same bucket.

// Bucket sort for floating-point numbers in [0, 1)
function bucketSort(arr) {
  const n = arr.length;
  if (n === 0) return arr;

  // Create n empty buckets
  const buckets = Array.from({ length: n }, () => []);

  // Distribute elements into buckets
  for (const num of arr) {
    const idx = Math.floor(num * n);  // bucket index = floor(num * n)
    buckets[Math.min(idx, n - 1)].push(num);  // clamp for num exactly = 1.0
  }

  // Sort each bucket (insertion sort for small buckets)
  for (const bucket of buckets) {
    bucket.sort((a, b) => a - b);  // insertion sort would be better here
  }

  // Concatenate all buckets
  return [].concat(...buckets);
}

bucketSort([0.897, 0.565, 0.656, 0.1234, 0.665, 0.3434]);
// → [0.1234, 0.3434, 0.565, 0.656, 0.665, 0.897]

bucketSort([0.897,0.565,0.656,0.1234,0.665,0.3434]) → [0.1234,0.3434,0.565,0.656,0.665,0.897]

Bucket sort for general ranges:

// Bucket sort for integers or floats in a general range [min, max]
function bucketSortGeneral(arr, numBuckets = arr.length) {
  if (arr.length === 0) return arr;
  const min = Math.min(...arr);
  const max = Math.max(...arr);
  if (min === max) return arr;  // all elements equal

  const range = max - min;
  const buckets = Array.from({ length: numBuckets }, () => []);

  for (const num of arr) {
    const idx = Math.floor(((num - min) / range) * (numBuckets - 1));
    buckets[idx].push(num);
  }

  for (const bucket of buckets) {
    bucket.sort((a, b) => a - b);
  }

  return [].concat(...buckets);
}

// LeetCode 164 — Maximum Gap
// After sorting, max gap is the maximum difference between consecutive elements.
// Bucket sort guarantees we only need to compare elements in adjacent buckets.
function maximumGap(nums) {
  if (nums.length < 2) return 0;
  const min = Math.min(...nums), max = Math.max(...nums);
  if (min === max) return 0;
  const n = nums.length;
  const bucketSize = Math.ceil((max - min) / (n - 1));
  const bucketCount = Math.floor((max - min) / bucketSize) + 1;

  const buckets = Array.from({ length: bucketCount }, () => ({ min: Infinity, max: -Infinity }));
  for (const num of nums) {
    const idx = Math.floor((num - min) / bucketSize);
    buckets[idx].min = Math.min(buckets[idx].min, num);
    buckets[idx].max = Math.max(buckets[idx].max, num);
  }

  let maxGap = 0, prevMax = min;
  for (const bucket of buckets) {
    if (bucket.min === Infinity) continue;  // empty bucket
    maxGap = Math.max(maxGap, bucket.min - prevMax);
    prevMax = bucket.max;
  }
  return maxGap;
}

Comparison: When to Use Each

Algorithm	Time	Space	Requirement	Best Use Case
Counting Sort	O(n + k)	O(k)	Non-neg integers, small range k	Scores, ages, small integers
Radix Sort LSD	O(d(n + b))	O(n + b)	Fixed-length integers or strings	32-bit integers, phone numbers
Radix Sort MSD	O(d(n + b))	O(n + b)	Strings, variable length OK	Dictionary sort, DNS names
Bucket Sort	O(n) avg	O(n + k)	Uniform distribution in known range	Float arrays, hash tables

Warning

These algorithms are only faster than O(n log n) under their specific assumptions. Counting sort with k = 10^9 needs a 4 GB array just for counts. Always verify the input constraints before choosing a non-comparison sort.

Key Differences from Comparison Sorts

Not bound by the O(n log n) lower bound — they exploit value information, not just comparisons
Counting sort: O(n + k) — excellent when k is small relative to n
Radix sort: stable, works well for integers; base 256 is faster in practice than base 10
Bucket sort: probabilistic O(n) — assumes uniform distribution, not a hard guarantee
All three require O(n) or more extra space — no in-place variants
None are general-purpose — they break down when assumptions are violated

Tip

In coding interviews, if you see constraints like "all numbers are in range [0, 10000]" or "input contains only lowercase letters," that is a hint that counting sort or radix sort is applicable and can give you O(n) instead of O(n log n).

Note

Counting sort is the engine inside radix sort. Radix sort processes d digits, using counting sort for each digit. The stability of counting sort is essential — without it, radix sort produces incorrect results because earlier digits must remain sorted when later digits are processed.