Fast Bucket Sort

vckicks 0 281 Views

A slightly modified version of Bucket Sort that uses LinkedLists and initializes buckets only when required. Results in massive speed improvements.

public static void Sort(int[] integers)
{
    //Verify input
    if (integers == null || integers.Length <= 1)
        return;

    //Find the maximum and minimum values in the array
    int maxValue = integers[0]; //start with first element
    int minValue = integers[0];

    //Note: start from index 1
    for (int i = 1; i < integers.Length; i++)
    {
        if (integers[i] > maxValue)
            maxValue = integers[i];

        if (integers[i] < minValue)
            minValue = integers[i];
    }

    //Create a temporary "bucket" to store the values in order
    //each value will be stored in its corresponding index
    //scooting everything over to the left as much as possible (minValue)
    //e.g. 34 => index at 34 - minValue
    LinkedList<int>[] bucket = new LinkedList<int>[maxValue - minValue + 1];
    
    //Move items to bucket
    for (int i = 0; i < integers.Length; i++)
    {
        if (bucket[integers[i] - minValue] == null)
            bucket[integers[i] - minValue] = new LinkedList<int>();

        bucket[integers[i] - minValue].AddLast(integers[i]);
    }

    //Move items in the bucket back to the original array in order
    int k = 0; //index for original array
    for (int i = 0; i < bucket.Length; i++)
    {
        if (bucket[i] != null)
        {
            LinkedListNode<int> node = bucket[i].First; //start add head of linked list

            while (node != null)
            {
                integers[k] = node.Value; //get value of current linked node
                node = node.Next; //move to next linked node
	            k++;
            }
        }
    }
}

Dani AI

Generated

Nice, practical tweak from — lazily creating buckets avoids allocating a lot of empty lists. Two important tradeoffs to keep in mind: LinkedList<T> creates one node object per element (GC pressure), and the algorithm still needs a bucket array sized by (max - min) so it becomes expensive when the numeric range is large.

public static void CountingSort(int[] a)
{
    if (a == null || a.Length <= 1) return;

    int min = a[0], max = a[0];
    for (int i = 1; i < a.Length; i++)
    {
        if (a[i] < min) min = a[i];
        else if (a[i] > max) max = a[i];
    }

    long range = (long)max - (long)min + 1;
    if (range > int.MaxValue || range > a.Length * 8) { Array.Sort(a); return; }

    int[] counts = new int[(int)range];
    for (int i = 0; i < a.Length; i++) counts[a[i] - min]++;

    int idx = 0;
    for (int i = 0; i < counts.Length; i++)
    {
        int c = counts[i];
        int value = i + min;
        while (c-- > 0) a[idx++] = value;
    }
}

Why this helps: replacing per-item linked-list nodes with a single int[] of counts removes allocation overhead and improves cache locality. The runtime is O(n + k) where k is the value range; that is great when k is O(n) but bad when k is huge. A simple heuristic: if range > n * 8 (tune the factor), fall back to Array.Sort or another comparison-based sort. Compute range as long and check it before allocating to prevent overflow or OutOfMemoryException.

If you must preserve insertion order for equal keys, keep bucket lists (as did) or implement a stable counting sort with prefix sums and an output buffer. If memory is constrained and k >> n, use a frequency map (e.g., Dictionary<int,int> then sort distinct keys) to avoid large arrays. On modern .NET, reuse buffers, use Span<T>/ArrayPool<T> and measure with Stopwatch — algorithm choice beats micro-optimizations.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.

Edit Preview