Bucket sort

Scatter values into a handful of buckets by value range, sort each small bucket, then read the buckets back in order.

The idea

Bucket sort divides the value range into a handful of buckets, drops each element into the bucket matching its value, then sorts each bucket (which is small, so any simple sort works) and concatenates the buckets in order. When values are spread evenly across the range, each bucket holds roughly n/k elements, so the small per-bucket sorts plus one linear distribution pass add up to close to linear time overall.

Code

public static int[] BucketSort(int[] a) {
    int min = a.Min(), max = a.Max();
    const int bucketCount = 5;
    var buckets = new List<int>[bucketCount];
    for (int i = 0; i < bucketCount; i++) buckets[i] = new List<int>();
    foreach (int x in a) {
        int idx = (int)((long)(x - min) * bucketCount / (max - min + 1));
        buckets[idx].Add(x);
    }
    var result = new List<int>();
    foreach (var bucket in buckets) {
        bucket.Sort();
        result.AddRange(bucket);
    }
    return result.ToArray();
}

Tips

• Works best when input is spread evenly across the range; a skewed input piles everything into one bucket and degrades toward O(n squared).
• Pick roughly as many buckets as there are elements for close to linear average time.

In the .NET library

Dictionary and HashSet lean on the same idea for O(1) average lookups: bucket by hash code instead of by value range, then only compare within the matching bucket.