Bucket Sort

Scatter values into range-buckets, sort each small bucket, then concatenate — O(n + k) average on uniform data.

Bucket sort is a scatter-then-gather sort. Divide the value range into a handful of buckets, drop each item into the bucket for its range, sort each bucket (usually with insertion sort), then concatenate the buckets in order. If the data is spread evenly, every bucket holds just a few items, so the per-bucket sorting is cheap — and the buckets come out already in order.

Scatter, sort, gather

1Create k empty buckets, each covering an equal slice of the value range.
2Scatter: map each value to its bucket index and append it there.
3Sort each bucket individually (insertion sort is ideal for tiny buckets).
4Gather: walk the buckets in order and concatenate them into the output.

function bucketSort(arr, k = arr.length) { // values in [0, 1)
  const buckets = Array.from({ length: k }, () => []);
  for (const v of arr) buckets[Math.floor(v * k)].push(v); // scatter
  const out = [];
  for (const b of buckets) {
    b.sort((a, c) => a - c); // sort each small bucket
    out.push(...b);          // gather in order
  }
  return out;
}

Why uniform data gives linear time

With n items spread evenly over k ≈ n buckets, each bucket holds about one item, so all the per-bucket sorting together is O(n). Add the O(n) scatter and O(k) gather and the average is O(n + k) — linear, like its non-comparison cousins counting and radix sort.

Skew is the enemy

The linear time assumes a roughly uniform distribution. If the data clusters, one bucket can swallow most of the items and its inner sort degrades to O(n²) — bucket sort's worst case. It works best when you know the values are spread evenly (e.g. uniform reals in [0, 1)).

OperationTimeSpace

Average (uniform) · few items per bucketO(n + k)O(n + k)

Worst (skewed) · one bucket holds everythingO(n²)O(n + k)

Check yourself

What assumption does bucket sort rely on to achieve its O(n + k) average time?