Bucket Sort Explained
Bucket Sort is a distribution sort that scatters elements into a number of buckets, sorts each bucket individually, then concatenates them. When the input is uniformly distributed, it achieves O(n) average time, making it a great fit for floating-point values spread evenly across a range.
How Bucket Sort works
1) Create k empty buckets covering equal sub-ranges of the input. 2) Distribute each element into the bucket for its range. 3) Sort each bucket (often with Insertion Sort, since buckets are small). 4) Concatenate the buckets in order. If elements are spread evenly, each bucket holds only a few items, so the per-bucket sort is cheap.
Complexity
Bucket Sort is O(n + k) average when data is uniform, but degrades to O(n²) if all elements land in one bucket (skewed data). It uses O(n + k) space and its stability depends on the per-bucket sort. It is most useful for normalized floating-point data such as values in [0, 1).
Bucket vs Counting vs Radix
These three non-comparison sorts are easy to confuse. Counting Sort buckets by exact integer value; Radix Sort buckets digit by digit; Bucket Sort buckets by value range and sorts within each. Choose Bucket Sort for uniformly distributed real numbers. Try the related Counting Sort and Radix Sort guides.
Frequently asked questions
What is the time complexity of Bucket Sort? +
When is Bucket Sort a good choice? +
See it in motion
Watch this algorithm and 9 others run step by step in our free interactive visualizer.
▶ Launch Visualiser