Bucket Sort
Distribution sort that distributes elements into buckets, sorts buckets individually, and concatenates.
Ready
1function bucketSort(arr):
2 create N buckets
3 for val in arr:
4 put val into bucket[idx]
5 for bucket in buckets:
6 sort(bucket)
7 return concatenate(buckets)
Complexity
TimeO(n + k)
SpaceO(n)
Assuming uniformly distributed input.