Bucket Sort is a distribution-based sorting algorithm that divides elements into multiple buckets, sorts each bucket individually, and then combines the results to produce the final sorted array.

The idea is to spread elements across buckets based on their value range so that each bucket contains a small subset of the data. If the data is uniformly distributed, this leads to near-linear time complexity.

The performance of Bucket Sort depends heavily on how the buckets are defined and how evenly the elements are distributed. In practice, it is often combined with another sorting algorithm, such as Insertion Sort, to sort individual buckets.

In this chapter, you will learn how Bucket Sort works, how to design effective bucket strategies, and when it can outperform traditional sorting algorithms.

Bucket sort is a distribution-based sorting algorithm. Instead of repeatedly comparing pairs of elements, it divides the input into a fixed number of "buckets" (or bins), distributes elements into those buckets based on their value, sorts each bucket individually, and then concatenates the results.

Here is the high-level idea:

You might notice a resemblance to counting sort. In fact, bucket sort is a generalization of counting sort. Counting sort creates one "bucket" per distinct value and only works with integers. Bucket sort creates a fixed number of buckets, each covering a range of values, and works with any data type, including floating point numbers. When bucket count equals the range of integer values, bucket sort reduces to counting sort.

Bucket sort works best when the input is uniformly distributed over a known range. If you know your data falls between 0 and 1, or between 0 and 1000, and the values are spread roughly evenly across that range, bucket sort shines. If all values cluster into a single bucket, it degrades to whatever sort you use inside the bucket.

Let us walk through the algorithm step by step, using the classic case of sorting floating point numbers in the range [0, 1).

Step 1: Create n Empty Buckets

Given n elements, create an array of n empty lists (buckets). Each bucket covers an equal slice of the value range.

For values in [0, 1) with n = 7 elements, the seven buckets cover these ranges:

Step 2: Distribute Elements into Buckets

For each element, compute its bucket index using the formula:

For a general range [minValue, maxValue], the formula becomes:

This maps each value to a bucket in O(1) time. You simply multiply, take the floor, and you have the index.

Step 3: Sort Each Bucket

Sort each bucket individually. Insertion sort is the traditional choice here, and for good reason. When elements are uniformly distributed, each bucket holds roughly n/k elements (where k is the number of buckets). With k = n, each bucket holds about 1 element on average, making insertion sort's O(m^2) cost per bucket negligible. Even when a bucket has a few elements, insertion sort is fast for small inputs due to low overhead.

Step 4: Concatenate All Buckets

Walk through the bucket array from index 0 to n-1, appending each bucket's sorted contents to the output. Since the buckets cover increasing value ranges, this produces a fully sorted array.

The diagram above simplifies the bucket indices for readability. In the actual algorithm, several buckets would be empty, and we skip over those during concatenation.

Let us trace through the algorithm with the array [0.42, 0.32, 0.23, 0.52, 0.25, 0.47, 0.51]. We have n = 7 elements, so we create 7 buckets.

Distribution Phase

For each element, we compute bucketIndex = floor(7 * value):

After distribution, the buckets look like this:

Sorting Phase

Sort each non-empty bucket individually:

Bucket 1 was already sorted. Bucket 2 needed one swap. Bucket 3 required a small rearrangement. This is what makes bucket sort fast: sorting many small groups is cheaper than sorting one large group.

Concatenation Phase

Walk through buckets 0 through 6 in order, collecting all elements:

The performance of bucket sort depends heavily on how evenly the input data is distributed across buckets.

Let us break down the average case more carefully. If we have n elements and k buckets, and the input is uniformly distributed, each bucket receives approximately n/k elements. Sorting one bucket with insertion sort costs O((n/k)^2). Across k buckets, the total sorting cost is:

Adding the O(n) distribution step and O(k) bucket creation:

When k = n (number of buckets equals number of elements), this becomes:

That is the magic number. Linear time sorting.

Stability

Whether bucket sort is stable depends on two things: the inner sorting algorithm and how elements are collected during concatenation. If you use a stable sort (like insertion sort) within each bucket and collect elements in bucket order, the overall sort is stable. If you use an unstable inner sort (like quicksort), bucket sort loses stability.

Bucket sort is not a general-purpose sorting algorithm. It excels in specific scenarios and falls flat in others.

Good Use Cases

Poor Use Cases