Bucket Sort

Concept

Both Counting Sort and Radix Sort are incredibly fast $O(N)$ algorithms, but they have a fatal, insurmountable flaw: They completely crash on Decimal Floats.
You cannot use 3.14 as an array index for a frequency bucket.

Bucket Sort is the final Non-Comparison sorting algorithm. It is explicitly designed to handle arrays of floating-point decimals that are uniformly distributed over a known range (e.g., numbers strictly between 0.0 and 1.0).

The Mechanism

Array: [0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12, 0.23, 0.68]

1. Create Buckets: We create an array of N empty lists (buckets). If there are 10 numbers, we create 10 empty buckets. Bucket 0 will handle 0.0 - 0.09. Bucket 1 will handle 0.10 - 0.19.
2. Scatter: We multiply the decimal by N to mathematically calculate exactly which bucket it belongs in!
   • 0.78 * 10 = 7.8. It belongs in Bucket 7.
   • 0.17 * 10 = 1.7. It belongs in Bucket 1.
3. Sort Individual Buckets: Notice that multiple numbers landed in Bucket 2 (0.26, 0.21, 0.23). We must sort the inside of this tiny bucket. We explicitly run Insertion Sort on the bucket. (Why Insertion Sort? Because the bucket only has 3 elements, and Insertion Sort is phenomenally fast on tiny datasets).
4. Gather: We just loop through the buckets from 0 to 9, and sequentially dump all their sorted contents into the final array!

Why is it O(N)?

This sounds like it uses a comparison sort (Insertion Sort) inside the buckets, so shouldn’t it be $O(N^2)$?

It relies on probability. If the numbers are uniformly distributed (spread out evenly), then mathematically, only 1 or 2 numbers will land in each bucket.
Sorting a bucket of 2 elements takes $O(1)$ time.
We have $N$ buckets. $N \times O(1)$ is $O(N)$.

Implementation

// Time Complexity: O(N) Average, O(N^2) Absolute Worst Case
// Space Complexity: O(N) (For the Buckets)

function bucketSort(nums: number[]): number[] {
    const n = nums.length;
    if (n <= 1) return nums;

    // 1. Create N empty buckets (arrays)
    const buckets: number[][] = Array.from({ length: n }, () => []);

    // 2. Scatter the decimals into the buckets
    for (let i = 0; i < n; i++) {
        // Assume numbers are strictly [0.0, 1.0)
        // Multiply by N to find the correct bucket index
        const bucketIndex = Math.floor(nums[i] * n);
        buckets[bucketIndex].push(nums[i]);
    }

    // 3. Sort each individual bucket, and gather the results
    const result: number[] = [];
    for (let i = 0; i < n; i++) {
        // Use standard JS sort (which handles the tiny arrays efficiently)
        buckets[i].sort((a, b) => a - b); 
        
        // Push all sorted elements from this bucket into the final result
        result.push(...buckets[i]);
    }

    return result;
}

The Catastrophic Worst Case

Bucket Sort’s $O(N)$ claim is entirely dependent on the data being uniformly distributed.

What if the array is [0.51, 0.52, 0.53, 0.54, 0.55]?
Because they all start with 0.5, every single number will mathematically calculate to Bucket 5.
Bucket 0, 1, 2, 3, and 4 will be completely empty.
Bucket 5 will hold the entire array!
The algorithm is forced to run Insertion Sort on the massive Bucket 5, completely degrading the time complexity to a catastrophic $O(N^2)$.

Interview Questions

Q: Can Bucket Sort handle integers, or is it strictly for decimals?
A: It can easily handle integers! You just need to mathematically map the integer range into the buckets. If the integers range from 0 to 100, and you have 10 buckets, you just divide the integer by 10 to find its bucket. (e.g., 45 / 10 = 4. It goes in Bucket 4).

Q: What is the defining difference between Counting Sort, Radix Sort, and Bucket Sort?
A:

• Counting Sort: Uses the literal mathematical value of the integer as the direct array index. $O(N)$ but requires massive RAM if the max number is huge.
• Radix Sort: Sorts the digits column by column from 1s to 100s. Fixes Counting Sort’s memory explosion issue.
• Bucket Sort: Groups values into numerical ranges (buckets) and explicitly sorts the insides of those buckets using an entirely different algorithm (Insertion Sort). The only one capable of handling decimals natively.