Bucket Sort

Drop each value into a bucket chosen by its value, count or digit, then read the buckets in order. No two values are compared, so it beats the O(n log n) floor when keys are small integers, evenly spread, or counts.

Overview

The idea

A comparison sort learns the order only by asking which of two values is bigger, and no such sort can beat O(n log n) in the worst case. Bucket sort skips the question. It computes a bucket index straight from the value, drops the value in, and reads the buckets back in order. Values in the same bucket are sorted separately, usually with a small comparison sort.

The bucket function is the whole design. Three choices cover the common problems.

Value range: index = value times k divided by the range — bucket sort proper — values are spread evenly over a known range
Exact value: one bucket per possible value — counting sort — keys are integers in a small range
One digit at a time, least significant first — radix sort — keys are integers or fixed-length strings with many digits
How often a value occurs: index = its count — frequency buckets — you need the most or least frequent items

Its cost is O(n + k) on average for n values and k buckets when the values spread evenly. When they all land in one bucket the inner sort does all the work, and the worst case is that sort's cost, O(n²) with insertion sort. So the first question to ask is how the values are spread.

Bucket sort on a value range

The trace sorts ten values in the range 0 to 1 into ten buckets, bucket = floor(value times 10). Each bucket is then sorted with insertion sort, and the buckets are read from 0 to 9.

0 — 0.07, 0.03 — 0.03, 0.07
1, 2
3 — 0.35, 0.31 — 0.31, 0.35
4 — 0.42, 0.48 — 0.42, 0.48
5 — 0.58 — 0.58
6 — 0.66 — 0.66
7
8 — 0.89 — 0.89
9 — 0.91 — 0.91

Reading the buckets in order gives the sorted list. Insertion sort inside a bucket is fine because the buckets are tiny when the values are spread evenly; if every value were between 0.30 and 0.39, all ten would sit in bucket 3 and the sort would be O(n²). Bucket sort is stable if the inner sort is stable and each bucket is filled in input order.

Counting sort: one bucket per value

When the keys are integers from 0 to k - 1, a bucket does not need to hold values, only a count. Count each key, then either write the keys back out in order or, to keep the sort stable, turn the counts into running totals and place each item at its final index, scanning the input from the end.

The trace sorts [3, 1, 4, 1, 0, 3] with keys 0 to 4.

Count — 1 — 2 — 0 — 2 — 1
Running total — 1 — 3 — 3 — 5 — 6

The running total says where each key's block ends: the 1s occupy indexes 1 and 2, the 3s indexes 3 and 4. Placing from the end of the input keeps equal keys in their input order. The cost is O(n + k) time and O(n + k) space, so it pays only when k is not much larger than n: exam scores or letters yes, 64-bit ids no. Harold Seward described counting sort, and its use in radix sort, in 1954.

Radix sort: one digit at a time

Radix sort runs a stable counting sort once per digit, starting with the last digit. Because each pass is stable, the order won by earlier passes survives ties in later passes. After the last pass the values are sorted.

start — 407 25 731 9 640 512 118 96
1 — ones digit — 640 731 512 25 96 407 118 9
2 — tens digit — 407 9 512 118 25 731 640 96
3 — hundreds digit — 9 25 96 118 407 512 640 731

With d digits and base k the cost is O(d(n + k)). For 32-bit integers, four passes over bytes (k = 256) sort in O(4(n + 256)), which is linear in n. It works for anything that reads as fixed-length digit strings: integers, dates, fixed-width codes.

Frequency buckets: Top K Frequent

Here the bucket index is how many times a value occurs. A value can occur at most n times, so n + 1 buckets are enough. Count with a hash map, put each value into the bucket for its count, then read the buckets from the highest count down until k values are collected.

The trace runs on [1, 1, 1, 2, 2, 3, 4, 4, 4, 4] with k = 2.

Values with that count — 3 — 2 — 1 — 4

Reading from bucket 4 downward gives 4, then 1: the two most frequent values, in O(n) time and O(n) space. A min-heap of size k gives the same answer in O(n log k), and quickselect on the counts gives O(n) expected; the buckets are the simplest linear answer. Sort Characters By Frequency is the same buckets read from the top and expanded, and Top K Frequent Words adds a sort of each bucket's words so ties come out alphabetically.

Maximum Gap: buckets as a pigeonhole argument

Maximum Gap asks for the largest difference between neighbors in sorted order, in linear time. Sorting costs O(n log n); buckets do it in O(n) without sorting.

Put n values into buckets of width w = floor((max - min) / (n - 1)), at least 1. The n - 1 gaps between sorted neighbors add up to max - min, so their average is (max - min) / (n - 1), and the biggest gap is at least that average, which is at least w. Two values in the same bucket differ by less than w. So the biggest gap is never inside a bucket: it is always between the largest value of one bucket and the smallest value of a later one. Keep only the minimum and maximum of each bucket, then scan the buckets once.

The trace runs on [1, 10, 5, 12, 3]: min 1, max 12, w = floor(11 / 4) = 2, 6 buckets.

0 — 1 to 2 — 1 — 1
1 — 3 to 4 — 3 — 3
2 — 5 to 6 — 5 — 5
3 — 7 to 8 — empty — empty
4 — 9 to 10 — 10 — 10
5 — 11 to 12 — 12 — 12

The candidate gaps are each bucket's min minus the previous non-empty bucket's max: 2, 2, 5, 2. The answer is 5, between 5 and 10. Note that the argument does not need an empty bucket; values spaced exactly evenly fill every bucket and the biggest gap still sits between two buckets.

Choosing between buckets and comparisons

Integers in a small range, such as 0 to 100 — counting sort — O(n + k)
Large integers or fixed-length strings — radix sort — O(d(n + k))
Real numbers spread evenly over a known range — bucket sort — O(n) average
Counts of items — frequency buckets — O(n)
Unknown distribution, arbitrary objects, custom comparators — a comparison sort — O(n log n)

> [!TIP] > When a problem says linear time and the values are integers, counts or evenly spread, the problem is asking for a bucket.

What you will be able to do

Explain why bucket, counting and radix sort can beat O(n log n), and when they cannot.
Write a stable counting sort and use it as the pass inside radix sort.
Solve Top K Frequent and Sort Characters By Frequency with frequency buckets in O(n).
Prove the Maximum Gap argument and code it.
Say when the value spread makes bucket sort a bad idea.

When to use it

Integer keys in a small known range, where counting sort is O(n + k)
Many-digit integers or fixed-length strings, where radix sort is O(d(n + k))
Values spread evenly over a known range, such as probabilities in 0 to 1
Problems about how often things occur: top k frequent, sort by frequency
Maximum Gap and other questions that ask for an O(n) answer that seems to need sorting

More Coding & DSA topics

Start free on Cariara · Coding problems · System design studio