Bucket Sort

Bucket sort (a.k.a Bin Sort) is a sorting algorithm that works by partitioning an array into a number buckets. Each bucket then sorted individually, either using a different sorting algorithm, or by recursively applying the bucket sorting algorithm.



									public static void BucketSort(ref int[] data)
{
	int minValue = data[0];
	int maxValue = data[0];

	for (int i = 1; i < data.Length; i++)
	{
		if (data[i] > maxValue)
			maxValue = data[i];
		if (data[i] < minValue)
			minValue = data[i];
	}

	List<int>[] bucket = new List<int>[maxValue - minValue + 1];

	for (int i = 0; i < bucket.Length; i++)
	{
		bucket[i] = new List<int>();
	}

	for (int i = 0; i < data.Length; i++)
	{
		bucket[data[i] - minValue].Add(data[i]);
	}
	
	int k = 0;
	for (int i = 0; i < bucket.Length; i++)
	{
		if (bucket[i].Count > 0)
		{
			for (int j = 0; j < bucket[i].Count; j++)
			{
				data[k] = bucket[i][j];
				k++;
			}
		}
	}
}
								


Example

									int[] data = new int[] { -1, 25, -58964, 8547, -119, 0, 78596 };
BucketSort(ref data);
								


Output

									-58964
-119
-1
0
25
8547
78596