SortingSorting
Bucket Sort
Distribute elements into buckets by value range, sort each bucket, and concatenate — linear on uniform data.
a
29
0
25
1
3
2
49
3
9
4
37
5
21
6
43
7
12
8
33
9
bucket 0 [3..12]
bucket 1 [13..21]
bucket 2 [22..31]
bucket 3 [32..40]
bucket 4 [41..49]
1/17Use k=5 buckets over the value range [3, 49]. Bucket sort works best when values are spread roughly uniformly, so each bucket gets few elements.
Element being placedBucket receiving itSorted
PseudocodeLearn Bucket Sort →
1k = number of buckets; lo = min(a); hi = max(a)2for x in a:3 b = floor((x - lo) / (hi - lo + 1) * k)4 buckets[b].append(x)5for each bucket: insertionSort(bucket)6a = concat(buckets)Variables
k5
lo3
hi49
Complexity
best O(n + k)
avg O(n + k)
worst O(n²)
space O(n + k)
Speed