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. With a uniform distribution, this produces near-linear time complexity.

Performance depends heavily on how the buckets are defined and how evenly the elements are distributed. Bucket sort is typically combined with another sorting algorithm, such as Insertion Sort, to sort individual buckets.

This chapter covers how Bucket Sort works, how to design effective bucket strategies, and when it outperforms traditional sorting algorithms.

Instead of repeatedly comparing pairs of elements, bucket sort 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:

Bucket sort resembles counting sort, and in fact generalizes it. 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. Data that falls between 0 and 1, or between 0 and 1000, with values spread roughly evenly across that range, suits bucket sort. When all values cluster into a single bucket, the algorithm's performance reduces to the performance of the inner sort.

The walkthrough below uses the canonical case: 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: one multiplication, one floor, with a clamp to handle the edge case where value == maxValue produces an index of n.

Step 3: Sort Each Bucket

Sort each bucket individually. Insertion sort is the traditional choice. When elements are uniformly distributed, each bucket holds roughly n/b elements (where b is the number of buckets). With b = n, each bucket holds about 1 element on average, so insertion sort's O(m^2) cost per bucket is negligible. Even when a bucket has a few elements, insertion sort is fast on 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. The actual algorithm leaves several buckets empty and skips them during concatenation.

The performance of bucket sort depends heavily on how evenly the input data is distributed across buckets. In this chapter, b refers to the number of buckets, to avoid clashing with k used in counting sort (value range) and radix sort (digit base).

A more detailed look at the average case: with n elements and b buckets, uniform distribution gives each bucket approximately n/b elements. Sorting one bucket with insertion sort costs O((n/b)^2). Across b buckets, the total sorting cost is:

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

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

With b = n buckets and uniform distribution, bucket sort runs in linear time.

Stability

Whether bucket sort is stable depends on the implementation, specifically the inner sorting algorithm and how elements are collected during concatenation. A stable inner sort (like insertion sort), combined with collecting elements in the original insertion order within each bucket, produces an overall stable sort. An unstable inner sort (like quicksort) makes bucket sort unstable.

For example, consider sorting [0.32a, 0.45, 0.32b] with 3 buckets. Both 0.32a and 0.32b land in the same bucket in that order. If the inner sort is insertion sort, the bucket stays [0.32a, 0.32b] and the final output preserves the original order. If the inner sort is quicksort, the bucket may end up as [0.32b, 0.32a], breaking stability.

When stability matters, pair bucket sort with insertion sort or another stable inner sort.

Bucket sort is not a general-purpose sorting algorithm. It performs well in specific scenarios and poorly in others.

Good Use Cases

Poor Use Cases