03 Bucket Sort Algorithm

Bucket sort uses hashing.

→ It makes assumptions about the data, like radix and counting sort.

→ Because it makes assumptions, can sort in O(n) time.

→ Performs the best when hashed values of items being sorted are evenly distributed, so there aren’t many collisions.

→ It is not a in-place sort.

→ Stability will depend on sort algorithm used to sort the buckets - ideally, you want a stable sort.

→ To achieve O(n), must have only one item per bucket.

→ Insertion sort is often used to sort the buckets, because it is fast when the number of items is small.

How does it work

Insertion sort is often used to sort the buckets, because it is fast algorithm when the number of items is small.