Bucket Sort

function bucketSort(arr) {
    if (arr.length === 0) return arr;

    // Find min and max values
    const min = Math.min(...arr);
    const max = Math.max(...arr);

    // Initialize buckets
    const bucketCount = Math.floor(Math.sqrt(arr.length)) + 1;
    const buckets = Array.from({ length: bucketCount }, () => []);

    // Distribute elements into buckets
    for (let i = 0; i < arr.length; i++) {
        const bucketIndex = Math.floor(
            ((arr[i] - min) / (max - min + 1)) * bucketCount
        );
        buckets[Math.min(bucketIndex, bucketCount - 1)].push(arr[i]);
    }

    // Sort each bucket and combine
    let sortedIndex = 0;
    for (let i = 0; i < buckets.length; i++) {
        // Sort individual bucket using insertion sort
        for (let j = 1; j < buckets[i].length; j++) {
            const key = buckets[i][j];
            let k = j - 1;

            while (k >= 0 && buckets[i][k] > key) {
                buckets[i][k + 1] = buckets[i][k];
                k--;
            }
            buckets[i][k + 1] = key;
        }

        // Copy sorted bucket back to original array
        for (let j = 0; j < buckets[i].length; j++) {
            arr[sortedIndex++] = buckets[i][j];
        }
    }

    return arr;
}

How Bucket Sort Works

Bucket Sort divides the input into several buckets, sorts each bucket individually, and then combines the sorted buckets to produce the final sorted array. It's like having multiple containers and sorting the contents of each container separately.

Algorithm Steps:

1. Create Buckets: Initialize empty buckets (arrays or lists)
2. Distribute Elements: Place each input element into appropriate bucket
3. Hash Function: Use a function to determine which bucket each element belongs to
4. Sort Buckets: Apply sorting algorithm to each non-empty bucket
5. Combine Results: Concatenate all sorted buckets in order

Bucket Distribution:

• Hash Function: Maps elements to bucket indices
• Uniform Distribution: Works best when elements are evenly distributed
• Range Division: Typically divides the range into equal intervals
• Bucket Count: Usually sqrt(n) or n/10 buckets for optimal performance

Key Characteristics:

• Stable: Maintains relative order of equal elements
• Not In-place: Requires additional space for buckets
• Distribution-dependent: Performance varies with input distribution
• Parallel-friendly: Each bucket can be sorted independently

Advantages:

• Linear time: O(n + k) when elements are uniformly distributed
• Stable sorting: Preserves order of equal elements
• Flexible: Can use different sorting algorithms for buckets
• Intuitive: Conceptually simple to understand

When to Use Bucket Sort:

• Uniformly distributed data: When elements are evenly spread across range
• Floating-point numbers: Works well with decimal values
• Large datasets: When linear time complexity is needed
• External sorting: Useful for sorting large files that don't fit in memory

Performance Insights:

• Best Case: O(n + k) with uniform distribution
• Worst Case: O(n²) when all elements fall into same bucket
• Average Case: O(n + k) for most practical distributions
• Bucket overhead: Empty buckets don't significantly impact performance

Comparison with Other Distribution Sorts:

• vs Counting Sort: More flexible with ranges, handles larger ranges
• vs Radix Sort: Different approach to digit-based sorting
• Hybrid approaches: Often combined with other sorting algorithms