Skip to content

Bucket sort

Problem

Implement bucket sort for numbers in the interval \([0,1]\).

Key trick

Distribute values into range-based buckets, sort each small bucket, and concatenate them.

Bucket sort is specialized to a known distribution and is not a general replacement for Timsort or merge sort.

Trap

The expected linear time assumes a reasonably uniform distribution; one overloaded bucket causes \(O(n^2)\) time here.

Why is it interesting?

It shows how known input distributions can outperform general comparison sorting.

Python solution

class sort_bucket_sort:
    def sort(self, nums: list[float]) -> list[float]:
        if not nums:
            return []

        if any(x < 0 or x > 1 for x in nums):
            raise ValueError("values must be in [0, 1]")

        n = len(nums)

        # Using one bucket per input value gives expected linear behavior
        # when the values are distributed reasonably uniformly.
        buckets: list[list[float]] = [[] for _ in nums]

        for x in nums:
            # Map the value to a proportional bucket.
            # `1.0` needs the `min` because its raw index would be `n`.
            idx = min(n - 1, int(x * n))
            buckets[idx].append(x)

        res = []

        # Values in earlier buckets cannot exceed values in later buckets.
        # Only values within each bucket still need sorting.
        for bucket in buckets:
            self._insertion_sort_in_place(bucket)
            res.extend(bucket)

        return res

    def _insertion_sort_in_place(
        self,
        nums: list[float],
    ) -> None:
        # Buckets are expected to be small, making insertion sort suitable.
        for i in range(1, len(nums)):
            val = nums[i]
            j = i - 1

            # Open a gap for `val`.
            while j >= 0 and nums[j] > val:
                nums[j + 1] = nums[j]
                j -= 1

            nums[j + 1] = val