Bucket Sort in Data Structure

Bucket Sort works by distributing elements of an array into a number of 'buckets', sorting each bucket individually (often using Insertion Sort), and then concatenating the sorted buckets to produce the final sorted array.

Algorithm Steps

• Create a fixed number of empty buckets.
• Distribute each input element into a bucket based on its value (commonly by scaling to the number of buckets).
• Sort each individual bucket, typically using Insertion Sort.
• Concatenate all buckets in order to get the final sorted array.

def bucket_sort(arr):
    if not arr:
        return arr
    num_buckets = len(arr)
    max_val, min_val = max(arr), min(arr)
    range_val = (max_val - min_val) / num_buckets + 1e-9

    buckets = [[] for _ in range(num_buckets)]
    for num in arr:
        idx = int((num - min_val) / range_val)
        buckets[idx].append(num)

    result = []
    for bucket in buckets:
        bucket.sort()   # insertion sort could be used here instead
        result.extend(bucket)
    return result

Complexity

Applications

• Sorting uniformly distributed floating-point numbers (e.g., values between 0 and 1).
• External sorting when data can be partitioned into ranges.
• Used in histogram-based data processing.