Bucket Sort
Scatter uniformly distributed values into ranged buckets, sort each tiny bucket, and concatenate. Averages O(n) when the data cooperates.
- Category
- Sorting
- Time complexity
- O(n) avg
- Space complexity
- O(n)
Pseudocode
make k ranged buckets drop each value in its bucket sort each bucket concatenate
Reference implementation
for v in a:
buckets[int(v * k)].append(v)
for b in buckets: b.sort()
return concat(buckets)