DSA — Bucket Sort

What is Bucket Sort?

Distributes elements into buckets, sorts each bucket, then concatenates.

def bucket_sort(arr):
    if not arr:
        return arr
    
    min_val = min(arr)
    max_val = max(arr)
    bucket_count = len(arr)
    bucket_range = (max_val - min_val) / bucket_count
    
    buckets = [[] for _ in range(bucket_count)]
    
    for num in arr:
        index = int((num - min_val) / bucket_range)
        if index == bucket_count:
            index -= 1
        buckets[index].append(num)
    
    result = []
    for bucket in buckets:
        result.extend(sorted(bucket))
    
    return result

Time Complexity

Case	Complexity
Best	O(n + k)
Average	O(n + k)
Worst	O(n²)

Where k is number of buckets.

Characteristics

• Stable sort (with stable inner sort)
• Works with floating point
• Performance depends on distribution
• Good for uniformly distributed data

Mini Practice

1. Implement bucket sort
2. Sort floating point numbers
3. Choose optimal bucket count
4. Compare with other sorts

Up Next

Continue with Depth First Search — DFS algorithm.