C# Bucket Sort
last modified November 6, 2026
In this article we implement the bucket sort algorithm in C#. We sort floating-point numbers, integers, and words, and show how the distribution of the data affects the speed.
Sorting is arranging the elements of a collection in a specific order, for instance from the smallest to the largest. A sorting algorithm is the sequence of steps that produces this order.
Bucket sort algorithm
Bucket sort divides the range of the values into intervals called buckets. Each element is put into the bucket of its interval. The buckets are sorted individually, usually with insertion sort, and then concatenated. Because the buckets cover consecutive intervals, the result is sorted.
| Property | Value |
|---|---|
| Average case | O(n + k) for uniformly distributed data and k buckets |
| Worst case | O(n²) with insertion sort, when most elements fall into one bucket |
| Extra memory | O(n + k) |
| Stable | yes, if the buckets are sorted with a stable algorithm |
Bucket sort is fast when the values are spread evenly over a known range. Then every bucket holds only a few elements.
C# bucket sort example
The classic example sorts floating-point numbers from the range [0, 1) using as many buckets as there are elements.
double[] vals = [0.42, 0.32, 0.23, 0.52, 0.25, 0.47, 0.51, 0.08, 0.91];
BucketSort(vals);
Console.WriteLine(string.Join(" ", vals));
static void BucketSort(double[] arr)
{
int n = arr.Length;
var buckets = new List<double>[n];
for (int i = 0; i < n; i++)
{
buckets[i] = [];
}
foreach (double x in arr)
{
buckets[(int)(x * n)].Add(x);
}
int k = 0;
foreach (var bucket in buckets)
{
InsertionSort(bucket);
foreach (double x in bucket)
{
arr[k++] = x;
}
}
}
static void InsertionSort(List<double> items)
{
for (int i = 1; i < items.Count; i++)
{
double key = items[i];
int j = i - 1;
while (j >= 0 && items[j] > key)
{
items[j + 1] = items[j];
j--;
}
items[j + 1] = key;
}
}
Each bucket is a List<double>.
buckets[(int)(x * n)].Add(x);
Multiplying a value from [0, 1) by n gives a bucket index from 0
to n - 1. For nine elements, 0.42 goes to bucket 3 and 0.47 to
bucket 4.
foreach (var bucket in buckets)
{
InsertionSort(bucket);
foreach (double x in bucket)
{
arr[k++] = x;
}
}
The buckets are sorted and their elements are written back to the array in the bucket order.
$ dotnet run 0.08 0.23 0.25 0.32 0.42 0.47 0.51 0.52 0.91
Sorting integers
For other data, the bucket index is computed from the minimum, the maximum, and the number of buckets. The next example sorts test scores into four buckets and prints them.
int[] scores = [78, 12, 95, 43, 67, 3, 88, 51, 29, 99, 64, 35];
BucketSort(scores, bucketCount: 4);
Console.WriteLine($"sorted: {string.Join(" ", scores)}");
static void BucketSort(int[] arr, int bucketCount)
{
int min = arr.Min();
int max = arr.Max();
double width = (max - min + 1) / (double)bucketCount;
List<int>[] buckets = [.. Enumerable.Range(0, bucketCount).Select(_ => new List<int>())];
foreach (int x in arr)
{
buckets[(int)((x - min) / width)].Add(x);
}
int k = 0;
for (int b = 0; b < bucketCount; b++)
{
buckets[b].Sort();
Console.WriteLine($"bucket {b}: {string.Join(" ", buckets[b])}");
buckets[b].CopyTo(arr, k);
k += buckets[b].Count;
}
}
The buckets are created with a collection expression.
double width = (max - min + 1) / (double)bucketCount;
The range from 3 to 99 contains 97 values, so each of the four buckets covers an interval of 24.25 values. Adding 1 to the range ensures that the maximum gets index 3, not 4.
buckets[(int)((x - min) / width)].Add(x);
The distance from the minimum divided by the bucket width gives the bucket index.
buckets[b].Sort();
Console.WriteLine($"bucket {b}: {string.Join(" ", buckets[b])}");
buckets[b].CopyTo(arr, k);
Here the buckets are sorted with the built-in List<T>.Sort
method and copied to the array.
$ dotnet run bucket 0: 3 12 bucket 1: 29 35 43 51 bucket 2: 64 67 bucket 3: 78 88 95 99 sorted: 3 12 29 35 43 51 64 67 78 88 95 99
Grouping words
Buckets do not have to be numeric intervals. In the next example, words are put into buckets by their first letter.
string[] words = ["melon", "apple", "kiwi", "mango", "banana", "avocado", "cherry", "blueberry", "lime"];
var buckets = new SortedDictionary<char, List<string>>();
foreach (string w in words)
{
char key = char.ToLowerInvariant(w[0]);
if (!buckets.TryGetValue(key, out var bucket))
{
bucket = [];
buckets[key] = bucket;
}
bucket.Add(w);
}
foreach (var (letter, bucket) in buckets)
{
bucket.Sort(StringComparer.Ordinal);
Console.WriteLine($"{letter}: {string.Join(", ", bucket)}");
}
string[] sorted = [.. buckets.Values.SelectMany(b => b)];
Console.WriteLine(string.Join(" ", sorted));
A SortedDictionary keeps the buckets ordered by their letter.
if (!buckets.TryGetValue(key, out var bucket))
{
bucket = [];
buckets[key] = bucket;
}
bucket.Add(w);
A new bucket is created the first time a letter is seen.
string[] sorted = [.. buckets.Values.SelectMany(b => b)];
The SelectMany method concatenates the sorted buckets. This
approach is common when the data should also be presented in groups, as in an
index or a phone book.
$ dotnet run a: apple, avocado b: banana, blueberry c: cherry k: kiwi l: lime m: mango, melon apple avocado banana blueberry cherry kiwi lime mango melon
Uniform vs skewed data
In the last example, we sort a million doubles with uniform and with skewed distribution. The array version stores all buckets in one output array.
#:property PublishAot=false
using System.Diagnostics;
const int N = 1_000_000;
var rnd = new Random(17);
double[] uniform = [.. Enumerable.Range(0, N).Select(_ => rnd.NextDouble())];
double[] skewed = [.. Enumerable.Range(0, N).Select(_ => Math.Pow(rnd.NextDouble(), 4))];
Measure("uniform", uniform);
Measure("skewed", skewed);
void Measure(string label, double[] data)
{
double[] a = [.. data];
var sw = Stopwatch.StartNew();
int largest = BucketSort(a);
long bucketMs = sw.ElapsedMilliseconds;
double[] b = [.. data];
sw.Restart();
Array.Sort(b);
long arrayMs = sw.ElapsedMilliseconds;
Console.WriteLine($"{label,-8} bucket sort {bucketMs,5} ms, Array.Sort {arrayMs,4} ms, " +
$"largest bucket {largest,7:N0}, same: {a.SequenceEqual(b)}");
}
static int BucketSort(double[] arr)
{
int n = arr.Length;
int[] counts = new int[n + 1];
foreach (double x in arr) counts[(int)(x * n) + 1]++;
int largest = counts.Max();
for (int i = 1; i <= n; i++) counts[i] += counts[i - 1];
double[] output = new double[n];
int[] next = (int[])counts.Clone();
foreach (double x in arr) output[next[(int)(x * n)]++] = x;
for (int b = 0; b < n; b++)
{
int lo = counts[b], hi = counts[b + 1];
for (int i = lo + 1; i < hi; i++)
{
double key = output[i];
int j = i - 1;
while (j >= lo && output[j] > key)
{
output[j + 1] = output[j];
j--;
}
output[j + 1] = key;
}
}
output.CopyTo(arr, 0);
return largest;
}
Raising a uniform random number to the fourth power crowds the values near zero; a quarter of them is less than 0.004.
foreach (double x in arr) counts[(int)(x * n) + 1]++; int largest = counts.Max(); for (int i = 1; i <= n; i++) counts[i] += counts[i - 1];
Instead of a million small lists, we count the bucket sizes. After the prefix
sums, bucket b occupies the positions from
counts[b] to counts[b + 1].
foreach (double x in arr) output[next[(int)(x * n)]++] = x;
The elements are distributed into their buckets in the output array. Then each bucket is sorted in place with insertion sort.
#:property PublishAot=false
File-based apps are published with Native AOT by default. The directive turns this off, so the release build does not pull in the AOT compiler package.
We run the program in the Release configuration. For uniform data, the largest
bucket has 9 elements and bucket sort is several times faster than
Array.Sort. For skewed data, a single bucket receives tens of
thousands of elements, and the insertion sort of that bucket makes bucket sort
several times slower than Array.Sort.
$ dotnet run -c Release benchmark.cs uniform bucket sort 40 ms, Array.Sort 146 ms, largest bucket 9, same: True skewed bucket sort 391 ms, Array.Sort 72 ms, largest bucket 31,681, same: True
Source
SortedDictionary<TKey, TValue> class
In this article we have implemented the bucket sort algorithm in C#.
Other sorting algorithms in C#:
- Bubble sort
- Selection sort
- Insertion sort
- Shell sort
- Merge sort
- Quick sort
- Heap sort
- Counting sort
- Radix sort
Author
List all C# tutorials.