The bucket sort is also known as bin sort. Bucket sort is a distribution sorting system where array elements are placed in different buckets. Each bucket is then sorted individually by either another sorting algorithm, or by applying recursive bucket sorting. An implementation of bucket sort using PHP can look like this:
function bucketSort(array &$data) {
$n = count($data);
if ($n <= 0)
return;
$min = min($data);
$max = max($data);
$bucket = [];
$bLen = $max - $min + 1;
$bucket = array_fill(0, $bLen, []);
for ($i = 0; $i < $n; $i++) {
array_push($bucket[$data[$i] - $min], $data[$i]);
}
$k = 0;
for ($i = 0; $i < $bLen; $i++) {
$bCount = count($bucket[$i]);
for ($j = 0; $j < $bCount; $j++) {
$data[$k] = $bucket[$i][$j];
$k++;
}
}
}
The time complexity of bucket sort is comparatively better than other comparison-based sorting algorithms. Here are the complexities for bucket sort:
Best time complexity |
Ω(n+k) |
Worst time complexity |
O(n2) |
Average time complexity |
Θ(n+k) |
Space complexity (worst case) |
O(n) |