Bucket Sort

Consider situation where we have

• numbers uniformly distributed in [0, 10^8)
• decimal numbers uniformly distributed in [0.0, 1.0]

How to solve efficiently

• Assuming k ~ n
  • Best case: $O(n)$ (Uniformly distributed)
  • Worst case: All items in single bucket -> Depends on the sorting algo
• Steps:
  1. Divide range in multiple buckets
  2. Put elements in appropriate bucket
  3. sort individual bucket
  4. Join them

Python

# assumption: not negative numker
# k -> number of buckets
def bucketSort(arr, k):
    rs = max(arr) + 1 # range size
    bucket = [[] for _ in range(k)]
    for x in arr:
        i = (k * x) // rs
        bucket[i].append(x)
    for i in range(k):
        bucket[i].sort()
    idx = 0
    for i in range(k):
        for j in range(len(bucket[i])):
            arr[idx] = bucket[i][j]
            idx += 1