jsschools

Bucket Sort

Distributes elements into a fixed number of buckets by value range, sorts each bucket independently, then concatenates the results.

Spec ↗

Syntax

bucketSort(arr, bucketCount?)

Parameters

NameTypeRequiredDescription
arr Array<number> Yes Array of numbers (typically in [0, 1) for the classic form, but any range works with normalisation).
bucketCount number No Number of buckets to use. Defaults to arr.length.

Returns

Array<number> — A new sorted array.

Examples

function bucketSort(arr, bucketCount = arr.length) {
  if (!arr.length) return [];
  const min = Math.min(...arr), max = Math.max(...arr);
  const buckets = Array.from({ length: bucketCount }, () => []);
  for (const x of arr) {
    const idx = Math.min(
      Math.floor(((x - min) / (max - min + 1)) * bucketCount),
      bucketCount - 1
    );
    buckets[idx].push(x);
  }
  return buckets.flatMap(b => b.sort((a, c) => a - c));
}

console.log(bucketSort([0.42, 0.32, 0.33, 0.52, 0.37, 0.47, 0.51]));
Output 
[ 0.32, 0.33, 0.37, 0.42, 0.47, 0.51, 0.52 ]

// Integer data spread across a range
function bucketSort(arr, k = arr.length) {
  if (!arr.length) return [];
  const min = Math.min(...arr), max = Math.max(...arr);
  const buckets = Array.from({ length: k }, () => []);
  for (const x of arr)
    buckets[Math.min(Math.floor(((x-min)/(max-min+1))*k), k-1)].push(x);
  return buckets.flatMap(b => b.sort((a, c) => a - c));
}

console.log(bucketSort([29, 25, 3, 49, 9, 37, 21, 43]));
Output 
[ 3, 9, 21, 25, 29, 37, 43, 49 ]

Notes

| Case | Time | Space | |---------|------------|-------| | Best | O(n + k) | O(n) | | Average | O(n + k) | O(n) | | Worst | O(n²) | O(n) | Worst case occurs when all elements land in the same bucket (highly skewed distribution). Average case assumes uniform distribution. The per-bucket sort is typically insertion sort. Bucket sort works well for floating-point numbers uniformly distributed in [0, 1). For integer inputs, counting sort or radix sort is usually preferred. The number of buckets k is a tuning parameter — k = n gives O(n) expected time.

See also