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.

									struct Bucket {
	int* Data;
	int Count;
};

int* AddItemInArray(int** arr, int count, int item) {
	int* newArr = malloc(sizeof(int) * (count + 1));

	for (int i = 0; i < count; i++) {
		newArr[i] = arr[i];
	}

	newArr[count] = item;

	return newArr;
}

void BucketSort(int* data, int count) {
	int minValue = data[0];
	int maxValue = data[0];

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

	int bucketLength = maxValue - minValue + 1;
	struct Bucket* bucket = malloc(sizeof(struct Bucket) * bucketLength);

	for (int i = 0; i < bucketLength; i++)
	{
		bucket[i] = *(struct Bucket*)malloc(sizeof(struct Bucket));
	}

	for (int i = 0; i < count; i++)
	{
		struct Bucket b = bucket[data[i] - minValue];
		if (b.Count < 0) {
			b.Count = 0;
		}

		bucket[data[i] - minValue].Data = AddItemInArray(b.Data, b.Count++, data[i]);
		bucket[data[i] - minValue].Count = b.Count;
	}

	int k = 0;
	for (int i = 0; i < bucketLength; i++)
	{
		int bucketSize = bucket[i].Count;

		if (bucketSize > 0)
		{
			for (int j = 0; j < bucketSize; j++)
			{
				data[k] = bucket[i].Data[j];
				k++;
			}
		}
	}
}

Example

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

Output