ZetCode

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.

PropertyValue
Average caseO(n + k) for uniformly distributed data and k buckets
Worst caseO(n²) with insertion sort, when most elements fall into one bucket
Extra memoryO(n + k)
Stableyes, 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.

Program.cs
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.

Program.cs
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.

Program.cs
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.

Program.cs
#: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#:

Author

I am Jan Bodnar, a programmer and technical writer. I have been writing programming tutorials at ZetCode since 2007 and have published eight e-books. See about the author.

List all C# tutorials.