How bucket sort works
- Find the smallest and the largest value.
- Create as many buckets as there are values. Each bucket covers an equal slice of the range between the smallest and the largest.
- Put every value into the bucket its size points to: (value - min) * buckets / range, with the decimals cut off.
- Sort each bucket. This code uses bubble sort, which is enough for the few values a bucket normally holds.
- Empty the buckets in order into one list. That list is the sorted result.
What the colours mean
The bucket row shows every bucket with its number in front. The one in use has a solid border. sortedList fills up as the buckets are emptied into it. The bars stay in their starting order until the last step, because this method builds a new array and leaves the input alone.
Bucket Sort time and space complexity
| Best case | Average case | Worst case | Extra space | Stable |
|---|---|---|---|---|
| O(n) | O(n) | O(n²) | O(n) | Yes |
Bucket sort is fast when the values are spread evenly, because each bucket then gets one or two of them and there is almost nothing to sort. It slows down when values crowd together. Type 1, 2, 3, 4, 5, 6, 7, 999 into the box: seven values land in bucket 0 and bubble sort does most of the work.
The space is the buckets plus the result list. With one bucket per value that is O(n).
The C# code
The listing beside the bars is the BubbleSort() and SortArray() methods from Bucket Sort in C#. The article explains the code and measures it with BenchmarkDotNet.
FAQ
Is bucket sort stable?
This version is. Values enter a bucket in their original order, and the bubble sort inside swaps only when the left value is strictly greater.
How many buckets should bucket sort use?
This code uses one bucket per value, which gives an average of one value per bucket when the data is evenly spread. Fewer buckets save memory and leave more sorting to do inside each one.
What is the difference between bucket sort and counting sort?
Counting sort has one counter per possible value and never sorts anything. Bucket sort has one bucket per slice of the range, so it copes with wide ranges and decimals, and it needs a second sort inside each bucket.