Updated on
Bucket sort is a sorting algorithm that spreads the elements of an array across several buckets by value, sorts each bucket, and joins the buckets back together in order. When the values are spread evenly, it runs in linear time on average, and in C# it takes little more than an array of lists.
Sorting is one of the most common programming problems that we have to solve, and each algorithm has its strengths and weaknesses. Below, we implement bucket sort in C#, analyze its time and space complexity, and measure when it pays off.
Let’s start.Â
What Is Bucket Sort?
Bucket/bin sort is a sorting algorithm that works by partitioning an array into several buckets. The bucket sort algorithm then sorts the contents of each bucket recursively or by applying different sorting algorithms.Â
In NIST’s Dictionary of Algorithms and Data Structures, bucket sort is “a distribution sort where input elements are initially distributed to several buckets”, with the bucket picked by an interpolation of the element’s key. In our code, that interpolation is one line of arithmetic that turns a value into a bucket index.
Bucket sort uses this principle to sort a list of elements:
- The algorithm sets up an array of empty buckets
- Each object from the unsorted array is scattered into its corresponding buckets
- Each bucket gets sorted individually
- Sorted items are gathered from each bucket in their correct order
Let’s take a deep dive and learn how bucket sort works.Â
How Does the Bucket Sort Algorithm Work?
To illustrate how the bucket sort algorithm works, let’s assume we intend to sort this array:
int[] array = {42, 6, 16, 4, 12, 24, 46, 17};
We need to divide these elements into buckets using an identifier. To make our example simple, let’s create buckets based on a range of ten values for each bucket: 0 – 9, 10 – 19, 20 – 29, 30 – 39, and 40 – 49.
Next, we are going to “scatter” the elements into those buckets based on their range:Â
- 0 – 9: 6, 4
- 10 – 19: 16, 12, 17
- 20 – 29: 24
- 30 – 39: (empty)
- 40 – 49: 42, 46
Now, we sort the items in each bucket using a different algorithm such as bubble sort (to keep our illustration simple):
- 0 – 9: 4, 6
- 10 – 19: 12, 16, 17
- 20 – 29: 24
- 30 – 39: (empty)
- 40 – 49: 42, 46
Finally, we gather the items from each bucket in the correct order, which completes the sorting process:Â
4, 6, 12, 16, 17, 24, 42, 46

Bucket sort on our example array: scatter the values into ten-value buckets, sort each bucket, then gather them in order.
Let’s learn how to implement the bucket sort algorithm in C#.
How to Implement Bucket Sort in C#?
To implement bucket sort in C#, we need an array of buckets, a formula that picks a bucket for each value, and a simple sort for the inside of each bucket.
First, we find the smallest and the largest value in the array. Together they give us the range the buckets have to cover.
Next, we create one List<int> bucket per element, so an array of 2,000 numbers gets 2,000 buckets. A value’s bucket index is its distance from the minimum, scaled to the number of buckets. The minimum lands in the first bucket, no value lands past the last one, and a smaller value never lands in a later bucket than a bigger one.
Then, we sort every bucket with bubble sort. When the values are spread evenly, most buckets hold zero, one or two elements, so this step costs very little.
Finally, we join the buckets in order, and the result is a sorted array.
We can implement the bucket sort algorithm in different ways. We are going to implement the algorithm in C# as we have discussed so far and try to improve its shortcomings by implementing an optimized solution.
Non-Optimized Bucket Sort Implementation in C#
First, in a BucketSortMethods class of a new console app, we are going to write a function int[] BubbleSort that takes a List<int> object and sorts its values using the bubble sort algorithm:
public static int[] BubbleSort(List<int> listInput)
{
for (int i = 0; i < listInput.Count - 1; i++)
{
for (int j = 0; j < listInput.Count - i - 1; j++)
{
if (listInput[j] > listInput[j + 1])
{
var temp = listInput[j];
listInput[j] = listInput[j + 1];
listInput[j + 1] = temp;
}
}
}
return listInput.ToArray();
}
Next, we are going to define a method called SortArray() in the same class as our entry point into the sorting algorithm. The method takes int[] array as its sole input and returns a sorted array:
public int[] SortArray(int[] array)
{
if (array.Length <= 1)
{
return array;
}
List<int> sortedList = [];
var minValue = array[0];
var maxValue = array[0];
for (int i = 1; i < array.Length; i++)
{
if (array[i] > maxValue)
maxValue = array[i];
if (array[i] < minValue)
minValue = array[i];
}
var numberOfBuckets = array.Length;
var range = (long)maxValue - minValue + 1;
List<int>[] bucket = new List<int>[numberOfBuckets];
for (int i = 0; i < numberOfBuckets; i++)
{
bucket[i] = [];
}
for (int i = 0; i < array.Length; i++)
{
var selectedBucket = (int)((array[i] - (long)minValue) * numberOfBuckets / range);
bucket[selectedBucket].Add(array[i]);
}
for (int i = 0; i < numberOfBuckets; i++)
{
int[] temp = BubbleSort(bucket[i]);
sortedList.AddRange(temp);
}
return sortedList.ToArray();
}
Let’s understand how this method works.
First, we check whether int[] array is empty or has a single element as our base case and skip the sorting process. The check comes before we read array[0], which would throw on an empty array:
if (array.Length <= 1)
{
return array;
}
Next, we are going to find the maximum and minimum elements in the array:
for (int i = 1; i < array.Length; i++)
{
if (array[i] > maxValue)
{
maxValue = array[i];
}
if (array[i] < minValue)
{
minValue = array[i];
}
}
Here, we loop through the array as we find the maxValue and minValue, which are going to come in handy when we create the buckets, which in this case, are List<int> objects:
var numberOfBuckets = array.Length;
var range = (long)maxValue - minValue + 1;
List<int>[] bucket = new List<int>[numberOfBuckets];
for (int i = 0; i < numberOfBuckets; i++)
{
bucket[i] = [];
}
We create one bucket for every element and let the buckets share the whole range between minValue and maxValue. In the walkthrough, we used buckets of ten values to keep the numbers round. For our eight-element example array, the code creates eight buckets instead, each covering a little over five values.
Now that we have the buckets ready, we are going to scatter the array values into the buckets we’ve created:
for (int i = 0; i < array.Length; i++)
{
var selectedBucket = (int)((array[i] - (long)minValue) * numberOfBuckets / range);
bucket[selectedBucket].Add(array[i]);
}
Here, we subtract minValue so that the smallest value maps to bucket 0. Then we multiply by the number of buckets and divide by the range, so even the largest value gets an index below the number of buckets. We do this arithmetic in long because maxValue - minValue overflows an int when an array holds both large negative and large positive numbers.
After initializing the buckets, we are going to invoke the BubbleSort() method we created earlier and pass each bucket. The method returns a sorted array, which we add at the end of the sorted list:Â
for (int i = 0; i < numberOfBuckets; i++)
{
int[] temp = BubbleSort(bucket[i]);
sortedList.AddRange(temp);
}
return sortedList.ToArray();
Finally, in a test method of an MSTest project that references our app, we can verify that the SortArray() method sorts a given unsorted array accurately:
var array = new int[] { 73, 57, 49, 99, 133, 20, 1 };
var expected = new int[] { 1, 20, 49, 57, 73, 99, 133 };
var sortFunction = new BucketSortMethods();
var sortedArray = sortFunction.SortArray(array);
Assert.IsNotNull(sortedArray);
CollectionAssert.AreEqual(expected, sortedArray);
Optimized Bucket Sort Implementation in C#
The bucket sort algorithm has a few weaknesses, which we are going to discuss soon. Our first version also does more work than it has to: it creates every bucket up front, even the ones that stay empty, and it runs bubble sort on every bucket.
We can drop the inner sort by giving every possible value its own bucket. A bucket then only ever holds copies of the same value, so there is nothing left to sort. We create a bucket only when a value needs it, and we use LinkedList<T> buckets, where AddLast() adds an element in constant time and we can read a bucket back from head to tail.
Let’s learn how to optimize our current implementation with a second method in the same class:Â
public int[] SortArrayOptimized(int[] array)
{
if (array.Length <= 1)
{
return array;
}
int maxValue = array[0];
int minValue = array[0];
for (int i = 1; i < array.Length; i++)
{
if (array[i] > maxValue)
{
maxValue = array[i];
}
if (array[i] < minValue)
{
minValue = array[i];
}
}
var range = (long)maxValue - minValue + 1;
LinkedList<int>[] bucket = new LinkedList<int>[range];
for (int i = 0; i < array.Length; i++)
{
if (bucket[array[i] - minValue] == null)
{
bucket[array[i] - minValue] = new LinkedList<int>();
}
bucket[array[i] - minValue].AddLast(array[i]);
}
var index = 0;
for (int i = 0; i < bucket.Length; i++)
{
if (bucket[i] != null)
{
LinkedListNode<int>? node = bucket[i].First;
while (node != null)
{
array[index] = node.Value;
node = node.Next;
index++;
}
}
}
return array;
}
SortArrayOptimized() is similar to SortArray() but has a few notable differences such as the use of LinkedList<int> objects instead of List<int> objects:
var range = (long)maxValue - minValue + 1; LinkedList<int>[] bucket = new LinkedList<int>[range];
The goal of this process is to store each array element in the bucket at index array[i] - minValue, so the smallest value goes to index 0 and no slot is wasted below it:
for (int i = 0; i < array.Length; i++)
{
if (bucket[array[i] - minValue] == null)
{
bucket[array[i] - minValue] = new LinkedList<int>();
}
bucket[array[i] - minValue].AddLast(array[i]);
}
We can see that the loop creates a new LinkedList<int> object the first time it meets a value. Every later copy of the same value goes to the end of that bucket when we call bucket[array[i] - minValue].AddLast(array[i]).
Next, we start the process of moving the elements from the bucket back into int[] array.
We achieve this by setting the index of the array to zero and iterating through the bucket as we add the sorted elements back into int[] array:
var index = 0;
for (int i = 0; i < bucket.Length; i++)
{
if (bucket[i] != null)
{
LinkedListNode<int>? node = bucket[i].First;
while (node != null)
{
array[index] = node.Value;
node = node.Next;
index++;
}
}
}
return array;
We start iterating from the head of the LinkedList<int> as we move to the next nodes as we add the values to the int[] array object. The loop terminates when the next node is null, and after the last bucket, the method returns the sorted array.Â
Next, we can verify that the SortArray()Â and SortArrayOptimized() methods return the same result when sorting an array:
[TestMethod]
public void GivenUnsortedArray_WhenArrayIsNotEmpty_ThenReturnSortedArray()
{
var expected = new int[] { 1, 20, 49, 57, 73, 99, 133 };
var sortFunction = new BucketSortMethods();
var sortNormal = sortFunction.SortArray([73, 57, 49, 99, 133, 20, 1]);
var sortOptimized = sortFunction.SortArrayOptimized([73, 57, 49, 99, 133, 20, 1]);
CollectionAssert.AreEqual(expected, sortNormal);
CollectionAssert.AreEqual(expected, sortOptimized);
}
With one bucket per value, bucket sort becomes what is sometimes called pigeonhole sort. It is a close relative of counting sort, which keeps a count per value instead of a list.
What Is the Time and Space Complexity of Bucket Sort?
Bucket sort runs in O(n + k) time in the best and the average case, where n is the number of elements and k the number of buckets, and in O(n²) time in the worst case. It needs O(n + k) extra space.
The average case comes with a condition: the values have to be spread evenly over their range. Then each bucket gets about one element, and sorting the buckets costs almost nothing. For 2,000 evenly spread random numbers, our SortArray() made 1,059 comparisons in total.
In the worst case, almost every value lands in the same bucket. When we changed one of those 2,000 numbers to 1,000,000,000, the other 1,999 all shared the first bucket, and bubble sort made 1,997,001 comparisons.
Bucket sort is stable when its inner sort is stable, and ours is. It does not sort in place.
Best-Case Time Complexity
Bucket sort encounters the best-case time complexity scenario when we scatter elements uniformly across the buckets, so each bucket holds at most one element and needs no sorting. The time it would take to sort the array is O(n + k) with n being the number of elements in the array and k being the number of buckets. As we’ve seen in the implementation section, the k buckets are what we pay for in memory.
Average-Case Time Complexity
When bucket sort encounters random array elements that are spread evenly over their range, it encounters an average-case time complexity scenario. Each bucket then holds only a few elements, and it would take O(n + k) time to sort the array with n being the number of elements in the array and k being the number of buckets. Random values alone are not enough, though: a few values far away from the rest can push everything else into a handful of buckets.
Worst-Case Time Complexity
This scenario occurs when most of the elements land in the same bucket. Then the “inner algorithm”, such as the bubble sort algorithm, has to sort almost the whole array, and it may need to carry out about N2/2 comparisons. Therefore, the bucket sort algorithm has a worst-case complexity of O(N2). A reversed array is not a problem by itself, because its values cover the same range and still land in different buckets. Our optimized version has no inner sort, so it always runs in O(n + k) time, with k being the range of values.
Advantages of Bucket Sort Algorithm
Bucket sort reduces the number of comparisons we make when sorting elements as we distribute them into different buckets and sort each bucket separately.Â
The algorithm can be fast when we scatter elements uniformly across all the buckets.Â
A comparison sort such as merge sort or quicksort can’t guarantee fewer than about n log n comparisons, because it learns about the order only by comparing elements. On evenly spread values, bucket sort gets under that limit by using the value itself to compute where an element goes. Radix sort uses the same idea, one digit at a time.
Disadvantages of Bucket Sort Algorithm
Like merge sort, it does not sort elements in place, as it needs O(n + k) extra space.
In the optimized version, k is the whole range of values, not the number of elements, so the memory cost depends on the values themselves. When we passed SortArrayOptimized() the four numbers 1, 2, 3 and 1,000,000,000, it allocated about 8 GB for a billion bucket slots. SortArray() sorted the same four numbers with less than 1 KB, because it creates one bucket per element.
At the far end, an array holding both int.MinValue and int.MaxValue would need 4,294,967,296 bucket slots, more than a .NET array can hold, so SortArrayOptimized() throws an OverflowException. That is why we compute the range as a long: in int arithmetic it would wrap around without any error.
The algorithm has a worst-case complexity of O(N2).
Bucket sort is only as stable as its inner sort. A stable sorting algorithm maintains the relative order of the array elements in case it encounters two equal values, unlike quicksort, which is unstable. Our bubble sort swaps only when the left value is strictly bigger, and we gather the buckets in order, so SortArray() is stable. SortArrayOptimized() is stable too, since AddLast() keeps equal values in the order the loop meets them.
Performance Tests
Let’s assess how bucket sort performs by measuring the time it takes for it to sort an array with BenchmarkDotNet.
First, let’s write a method in our BucketSortMethods class to generate a set of random array elements:
public static int[] CreateRandomArray(int size)
{
var array = new int[size];
var rand = new Random();
for (int i = 0; i < size; i++)
array[i] = rand.Next(1, size);
return array;
}
The CreateRandomArray() method takes an integer as its sole input. Using the inbuilt Random class, we generate random numbers between 1 and the array size, so they are spread evenly over their range.
Next, we are going to define a method in the same class that generates a sequence of elements. This method simulates a scenario where we have a sorted array:
public static int[] CreateSortedArray(int size)
{
var array = new int[size];
for (int i = 0; i < size; i++)
array[i] = i;
return array;
}
SortArrayOptimized() writes the sorted values back into the array we pass in, and BenchmarkDotNet runs each benchmark method many times. If all those calls shared one array, the first call would sort it, and every later call would get sorted input, whatever the row’s label says. So, we generate each input once, and each of the three methods copies it before sorting. We also add Array.Sort() as the baseline:
public class BucketSortBenchmarks
{
private readonly BucketSortMethods _sorter = new();
private int[] _source = [];
private int[] _work = [];
[Params(200, 2_000, 20_000)]
public int Size { get; set; }
[Params("Random", "Sorted")]
public string Input { get; set; } = "Random";
[GlobalSetup]
public void Setup()
{
_source = Input == "Random"
? BucketSortMethods.CreateRandomArray(Size)
: BucketSortMethods.CreateSortedArray(Size);
_work = new int[Size];
}
[Benchmark]
public int[] SortArray()
{
_source.CopyTo(_work, 0);
return _sorter.SortArray(_work);
}
[Benchmark]
public int[] SortArrayOptimized()
{
_source.CopyTo(_work, 0);
return _sorter.SortArrayOptimized(_work);
}
[Benchmark(Baseline = true)]
public int[] ArraySort()
{
_source.CopyTo(_work, 0);
Array.Sort(_work);
return _work;
}
}
Setup() runs before the measured calls, for every benchmark method and every Size and Input pair. The copy adds the same small cost to all three methods.
The class goes in its own file in our console app. We add the BenchmarkDotNet package to the app, start the class file with using BenchmarkDotNet.Attributes;, and call BenchmarkRunner.Run<BucketSortBenchmarks>(); from its Program.cs, after using BenchmarkDotNet.Running;. Let’s run it in Release mode and look at the results:
| Method | Size | Input | Mean | Error | StdDev | Ratio | RatioSD | |------------------- |------ |------- |---------------:|-------------:|-------------:|------:|--------:| | SortArray | 200 | Random | 4,401.3 ns | 72.11 ns | 67.45 ns | 3.09 | 0.05 | | SortArrayOptimized | 200 | Random | 3,137.3 ns | 7.97 ns | 7.46 ns | 2.20 | 0.01 | | ArraySort | 200 | Random | 1,424.3 ns | 4.51 ns | 4.22 ns | 1.00 | 0.00 | | | | | | | | | | | SortArray | 200 | Sorted | 5,028.5 ns | 88.08 ns | 78.08 ns | 9.67 | 0.15 | | SortArrayOptimized | 200 | Sorted | 2,736.0 ns | 40.24 ns | 33.60 ns | 5.26 | 0.07 | | ArraySort | 200 | Sorted | 520.2 ns | 2.68 ns | 2.51 ns | 1.00 | 0.01 | | | | | | | | | | | SortArray | 2000 | Random | 53,462.8 ns | 234.04 ns | 195.43 ns | 1.11 | 0.01 | | SortArrayOptimized | 2000 | Random | 41,263.1 ns | 816.33 ns | 801.75 ns | 0.86 | 0.02 | | ArraySort | 2000 | Random | 48,077.5 ns | 605.75 ns | 566.62 ns | 1.00 | 0.02 | | | | | | | | | | | SortArray | 2000 | Sorted | 57,667.0 ns | 796.20 ns | 705.81 ns | 8.28 | 0.11 | | SortArrayOptimized | 2000 | Sorted | 32,609.6 ns | 650.44 ns | 722.96 ns | 4.68 | 0.10 | | ArraySort | 2000 | Sorted | 6,964.5 ns | 41.59 ns | 34.73 ns | 1.00 | 0.01 | | | | | | | | | | | SortArray | 20000 | Random | 2,274,225.6 ns | 18,210.55 ns | 17,034.16 ns | 2.61 | 0.03 | | SortArrayOptimized | 20000 | Random | 2,026,048.8 ns | 39,474.49 ns | 45,458.88 ns | 2.33 | 0.05 | | ArraySort | 20000 | Random | 870,690.6 ns | 7,873.22 ns | 7,364.61 ns | 1.00 | 0.01 | | | | | | | | | | | SortArray | 20000 | Sorted | 1,727,689.3 ns | 13,965.34 ns | 13,063.19 ns | 15.13 | 0.21 | | SortArrayOptimized | 20000 | Sorted | 1,141,573.7 ns | 18,436.75 ns | 17,245.75 ns | 10.00 | 0.19 | | ArraySort | 20000 | Sorted | 114,219.0 ns | 1,482.73 ns | 1,386.94 ns | 1.00 | 0.02 |
Array.Sort() is the fastest in five of the six groups. At 2,000 random numbers, the three methods finish close together, between about 41 and 53 microseconds. At 20,000 elements, the built-in sort is about two and a half times faster than our two versions on random input and about 10 to 15 times faster on sorted input.
The O(n + k) average doesn’t show up in these numbers. The visible difference is memory. For 20,000 random elements, SortArray() allocated about 2 MB per call for its 20,000 small lists, and SortArrayOptimized() about 1.6 MB for its linked lists. Array.Sort() sorted the array where it was and allocated nothing.
Of our two versions, the optimized one is faster in all six groups. At 20,000 elements, it needs about 10 percent less time on random input and about a third less on sorted input.
Conclusion
In this article, we have learned how bucket sort works in C#. We can use it in scenarios where we have control over the range of values that we intend to sort, and where those values are spread evenly. When they are not, merge sort keeps its O(n log n) in every case and quick sort on average, while bucket sort can fall to O(n²). For everyday code, Array.Sort() beat both of our versions in five of the six groups of our benchmark.
Tested with .NET 10.0.10, BenchmarkDotNet 0.15.8 and MSTest 4.5.2.
