cf.completefrontend
SORTING · ADVANCED

Bucket sort

Spread the values into a few ranges (buckets), sort each small bucket, then join the buckets in order.

Time O(n + b) on evenly spread dataSpace O(n + b)2 practice problemsStep-through picture

The idea

Bucket sort splits the range of values into equal slices called buckets. For values from 0 to 100 with 5 buckets, the buckets cover 0 to 20, 20 to 40, and so on. Each value goes into the bucket for its slice.

Every value in bucket 0 is smaller than every value in bucket 1, so once each bucket is sorted on its own, joining them in order gives a sorted list. Each bucket is small, so sorting it is cheap.

When the values are spread evenly, each bucket gets only a few items and the whole sort takes about O(n) time. When most values crowd into one bucket, it is no faster than sorting that one bucket normally.

An everyday example

Sorting a pile of coins by size into jars first

You have a jumble of coins to line up from smallest to largest. First you drop them into a few jars labeled "tiny", "small", "medium", and "large" by a quick look. Then you sort the few coins in each jar, which is easy. Finally you empty the jars in order, tiny first, onto the table.

How the example maps to the code
In the exampleIn the code
The labeled jarsbuckets
Deciding which jar a coin goes inMath.floor((value - min) / width)
Sorting the few coins in one jarbucket.sort((a, b) => a - b)
Emptying the jars in orderresult.push(...bucket)

From the slow way to bucket sort

  1. Counting sort gives every possible value its own slot. That fails for values like prices with cents or measurements like 0.38, because there are far too many possible values. But we can still use the same trick in a rougher way: instead of one slot per value, use one slot per range of values.
  2. Split the range from min to max into bucketCount equal slices, each width wide. A value's slice is Math.floor((value - min) / width), one subtraction and one division, no comparisons. Every value in slice 0 is smaller than every value in slice 1, and so on, so the slices are already in order relative to each other.
  3. Inside a slice the values are still mixed up, so each bucket needs a normal sort. The point is that each bucket is small. If n values are spread evenly over n buckets, each bucket gets about one value, and sorting a handful of items is close to free.
  4. So the whole job is: spread the values into buckets by range, sort each bucket on its own, and join the buckets in order. The spreading and joining are linear, and the sorting is cheap when the data is spread out. That loop is bucket sort.

How it works

  1. Find min and max of the values.
  2. Split the range into bucketCount slices of size width = (max - min) / bucketCount.
  3. Put each value into bucket Math.floor((value - min) / width), using the last bucket for max itself.
  4. Sort each bucket on its own.
  5. Join the buckets in order into result.

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…
See every step at onceThe same run, laid out side by side
Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor (opens in a new tab)
  1. function bucketSort(items, bucketCount = 5) {
  2. if (items.length === 0) return items;
  3. const min = Math.min(...items);
  4. const max = Math.max(...items);
  5. const width = (max - min) / bucketCount || 1;
  6. const buckets = Array.from({ length: bucketCount }, () => []);
  7. for (const value of items) {
  8. const index = Math.min(bucketCount - 1, Math.floor((value - min) / width));
  9. buckets[index].push(value);
  10. }
  11. const result = [];
  12. for (const bucket of buckets) {
  13. bucket.sort((a, b) => a - b);
  14. result.push(...bucket);
  15. }
  16. return result;
  17. }

How fast it is

TimeO(n + b) on evenly spread data
Extra memoryO(n + b)

b is the number of buckets. Spreading and joining touch each value once. Sorting is cheap when each bucket is small, and costs a full sort when one bucket gets nearly everything.

  • Best caseO(n + b)

    Values are spread evenly, like [0.1, 0.35, 0.6, 0.85] with 4 buckets: each bucket gets exactly one value, so the bucket sorts cost almost nothing.

  • Average caseO(n + b)

    Values drawn evenly at random from a range, with about as many buckets as values. The expected size of each bucket stays a small constant.

  • Worst caseO(n log n)

    Most values crowd into one bucket, like [1, 2, 3, 1000] with 4 buckets: 1, 2, and 3 all land in bucket 0, so it is just a normal sort of that bucket.

Common mistakes

  • Computing the index as Math.floor(value / width) without subtracting min. Values that don't start at 0 land in the wrong buckets or past the end.
  • Forgetting that max gets index bucketCount, one past the last bucket. Clamp it.
  • Dividing by a width of 0 when every value is the same, giving NaN indexes.
  • Using it on badly skewed data and expecting O(n). If most values crowd together, you have only moved the sorting into one bucket.

When to use it

Look for these clues in a problem:

  • The values are spread fairly evenly over a known range, such as random numbers or percentages.
  • The question groups values by range first, such as "items with the same frequency" or "scores in each band".
  • You need to compare only neighboring values in sorted order, such as the largest gap, and want to avoid a full sort.

Check yourself

Answer each one in your head first, then open it.

Why must min be subtracted before dividing by width?

Bucket 0 must start at the smallest value. For values from 100 to 140 with 4 buckets, width is 10, and dividing without subtracting gives indexes from 10 to 14, all past the last bucket.

Which bucket does the maximum value land in without the Math.min clamp?

Bucket number bucketCount, because (max - min) / width equals bucketCount exactly. That index doesn't exist, so push throws.

If all 1,000 values land in one bucket, how fast is it?

As fast as sorting that one bucket: O(n log n) with the built-in sort. The spreading and joining added work but saved nothing.

Why is bucket sort correct even when the buckets are uneven?

Correctness only needs the bucket order to match the value order and each bucket to be sorted. Even spread only affects the speed.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

Not started

0 of 2 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

medium

hard

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

The key fact is that the bucket index never goes down as the value goes up. (value - min) / width grows with value, Math.floor keeps that order (it never turns a bigger number into a smaller one), and clamping to bucketCount - 1 only touches the top. So if a < b, then a's bucket is the same as b's or earlier.

That gives the rule the join depends on: every value in bucket i is at most every value in bucket i + 1. After each bucket is sorted, writing bucket 0, then bucket 1, and so on puts values from different buckets in the right order (by the rule) and values from the same bucket in the right order (by the bucket's sort).

Every value goes into exactly one bucket and every bucket is written exactly once, so result holds exactly the input values. Both loops end after n values and bucketCount buckets. The speed depends on how even the buckets are; correctness does not.

Going deeper

3 more ideas

Why joining sorted buckets gives a sorted list

The bucket index grows with the value: a bigger value never lands in an earlier bucket. So every value in bucket b is at most every value in bucket b + 1. Inside each bucket the values are sorted. Putting the buckets end to end keeps both facts, so the whole list is in order.

How long it takes

Spreading and joining are O(n + buckets). If the values are even, each bucket gets about n / buckets items, and sorting all of them costs little; with as many buckets as items it is about O(n) in total. If everything lands in one bucket, the cost is just sorting that bucket, O(n log n) or O(n²) with insertion sort.

Buckets by count, not by value

A common variation uses one bucket per possible count. To list items by how often they appear, make buckets 0..n and put each item in the bucket for its count. Reading the buckets from high to low gives the most frequent items first, in O(n) time with no comparison sort at all.

Work it by hand

Every step in a table, with why

Sort 8 values into 4 buckets. Watch 47, the maximum, get clamped into the last bucket.

items = [14, 41, 7, 33, 22, 38, 9, 47], bucketCount = 4

StepStepvalueindexbuckets / resultWhat happensWhy
1Setup--4 empty bucketsmin = 7, max = 47, width = 10(47 - 7) / 4 is 10, so the buckets cover 7 to 17, 17 to 27, 27 to 37, and 37 to 47.
2Spread1400: [14](14 - 7) / 10 = 0.7Math.floor(0.7) is 0.
3Spread4133: [41](41 - 7) / 10 = 3.441 goes to the last bucket.
4Spread700: [14, 7](7 - 7) / 10 = 0The minimum always lands in bucket 0. It goes after 14, because buckets keep arrival order.
5Spread3322: [33](33 - 7) / 10 = 2.6Bucket 2.
6Spread2211: [22](22 - 7) / 10 = 1.5Bucket 1.
7Spread3833: [41, 38](38 - 7) / 10 = 3.1Bucket 3 now has two values, out of order.
8Spread900: [14, 7, 9](9 - 7) / 10 = 0.2Bucket 0 has three values.
9Spread4733: [41, 38, 47]4 clamped to 3(47 - 7) / 10 is exactly 4, one past the last bucket. Math.min(bucketCount - 1, ...) moves it into bucket 3.
10Join-0[7, 9, 14]Sort bucket 0, append[14, 7, 9] becomes [7, 9, 14] and is pushed into result.
11Join-1[7, 9, 14, 22]Append bucket 1A one-item bucket is already sorted.
12Join-2[7, 9, 14, 22, 33]Append bucket 2Everything in bucket 2 is bigger than everything before it.
13Join-3[7, 9, 14, 22, 33, 38, 41, 47]Sort bucket 3, append[41, 38, 47] becomes [38, 41, 47]. The loop over buckets ends.

It returns [7, 9, 14, 22, 33, 38, 41, 47]. The biggest bucket had 3 items, so the per-bucket sorts were tiny. The spreading took one pass of 8 values and the joining one pass of 4 buckets.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
Bucket sortO(n + b)O(n + b)Values are numbers spread fairly evenly over a known range, including decimals, and you can pick the bucket count.
Counting sortO(n + k)O(n + k)Values are whole numbers in a small range. Each value gets its own slot, so no bucket needs sorting.
Radix sortO(d × n)O(n)Whole numbers with a large range and few digits, where even spread is not guaranteed.
Comparison sort (built-in sort)O(n log n)O(n)Nothing is known about how the values are spread, or the data is strings or objects.

Extra memory: O(n + b): b bucket arrays that together hold all n values, plus result with n values.

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for Bucket sort and the other approaches, on a scale where each line up is 10 times more steps.
  • Bucket sort, Counting sort O(n + b)
  • Radix sort O(d × n)
  • Comparison sort (built-in sort) O(n log n)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
Bucket sort202,0002 million
Counting sort202,0002 million
Radix sort1001 million1 trillion
Comparison sort (built-in sort)339,96620 million

Inputs that need care

5 tricky inputs
An empty list
The first line returns it. Without that check, Math.min() of nothing is Infinity and the width would be NaN.
All equal: [4, 4, 4]
(max - min) / bucketCount is 0, so || 1 sets width = 1. Every value lands in bucket 0, and the result is [4, 4, 4].
Negative values: [-5, 3, -1, 0]
Subtracting min shifts everything to start at 0, so negatives work: the result is [-5, -1, 0, 3].
The maximum value
(max - min) / width is exactly bucketCount, one past the end. The Math.min clamp puts it in the last bucket; without it, buckets[4].push would throw.
Skewed data: [1, 2, 3, 1000]
One far-away value stretches the range, so the others all share bucket 0. The answer is still right, but the speed-up is gone. Choose bucket edges from the data, or use a comparison sort.

Variations and follow-ups

Twists interviewers add

Insertion sort inside buckets

The classic version sorts each bucket with insertion sort. With n buckets and evenly spread values, the expected total cost is O(n), because each bucket is tiny and insertion sort is fast on tiny lists.

Buckets from samples

For uneven data, take a small random sample, sort it, and use its values as bucket edges. Each bucket then gets about the same number of values. This is called sample sort and is used to split huge sorts across many machines.

Values in [0, 1)

For fractions from 0 up to 1, the index is simply Math.floor(value * bucketCount), with no min or width needed. This is the textbook setting where bucket sort is proven to be linear on average.

Histograms

Drop the sorting and keep only how many values land in each bucket. That is a histogram, the same spreading step used to draw value distributions in charts.

In an interview

Spot it, explain it, answer follow-ups
  • Spot it when the problem says values are "uniformly distributed", gives a range like "floats in [0, 1)", or asks for something like the maximum gap between neighbors in sorted order in linear time.
  • Explain it as "split the range into equal slices, sort each slice, and join". State clearly that the linear time is an average that assumes evenly spread values.
  • Test by hand with the maximum value (the clamp), with all-equal values (the zero width), and with one far outlier (the bad case).
  • A common follow-up is the maximum gap problem: the biggest difference between neighbors in sorted order. With n - 1 buckets of width (max - min) / (n - 1), the biggest gap is at least one bucket wide, so it can't be inside a bucket. Keep only each bucket's smallest and largest value and compare across buckets: O(n) with no full sort.

Where frontend code uses it

The same idea in real UI code
  • Histogram charts are the first half of bucket sort: values are dropped into equal-width bins and the bins are drawn in order.
  • Canvas and map apps split the screen into grid cells (spatial buckets) so a click or a nearby-point search only checks the items in a few cells.
  • Showing the most-used emoji or tags first is often done with buckets by count rather than a full sort.

Related algorithms