Bucket Sort

Bucket sort, or bin sort, is a sorting algorithm that works by partitioning an array into a number of buckets. Each bucket is then sorted individually, either using a different sorting algorithm, or by recursively applying the bucket sorting algorithm. It is a distribution sort, and is a cousin of radix sort in the most to least significant digit flavour. Bucket sort is a generalization of pigeonhole sort. Since bucket sort is not a comparison sort, the O(n log n) lower bound is inapplicable. The computational complexity estimates involve the number of buckets.

Bucket sort works as follows:

• Set up an array of initially empty "buckets."
• Scatter: Go over the original array, putting each object in its bucket.
• Sort each non-empty bucket.
• Gather: Visit the buckets in order and put all elements back into the original array.

public IList BucketSort(IList arrayToSort)
{
    if (arrayToSort == null || arrayToSort.Count == 0) return arrayToSort;

    object max = arrayToSort[0];
    object min = arrayToSort[0];


    for (int i = 0; i < arrayToSort.Count; i++)
    {

        if (((IComparable)arrayToSort[i]).CompareTo(max) > 0)
        {
            max = arrayToSort[i];
        }

        if (((IComparable)arrayToSort[i]).CompareTo(min) < 0)
        {
            min = arrayToSort[i];
        }
    }
    ArrayList[] holder = new ArrayList[(int)max - (int)min + 1];

    for (int i = 0; i < holder.Length; i++)
    {
        holder[i] = new ArrayList();
    }

    for (int i = 0; i < arrayToSort.Count; i++)
    {
        holder[(int)arrayToSort[i] - (int)min].Add(arrayToSort[i]);
    }

    int k = 0;

    for (int i = 0; i < holder.Length; i++)
    {
        if (holder[i].Count > 0)
        {
            for (int j = 0; j < holder[i].Count; j++)
            {
                arrayToSort[k] = holder[i][j];
                RedrawItem(k);
                pnlSamples.Refresh();
                if (chkCreateAnimation.Checked)
                    SavePicture();
                k++;
            }
        }
    }

    return arrayToSort;
}