Bucket Sort

Bucket sort is a distribution-based sorting algorithm, not a comparison sort. It scatters values into ordered buckets, sorts the values within each bucket, and gathers the buckets in order to produce the result. It works especially well when values are spread fairly evenly across a known range. This scatter-gather approach is useful when a suitable mapping from values to buckets is available.

Bucket Sort Algorithm

Choose k buckets to cover the input range, then map each value to the bucket for its interval. For values in [0, 1), a convenient zero-based rule is floor(k * x): bucket j covers [j/k, (j+1)/k). The upper limit is excluded, so every accepted value maps to an index from 0 through k - 1. Values outside this domain need normalization or a different mapping; the formula is not universal.

The procedure is:

1. Create k buckets for the chosen range.
2. Visit each input value x and place it in bucket floor(k * x).
3. Sort each bucket independently. Insertion sort is often used for small buckets, while other local sorting methods are also possible.
4. Traverse buckets in index order and append their sorted values to the result.

The bucket mapping preserves order between buckets: every value in bucket j is less than every value in bucket j + 1. Sorting inside each bucket handles the values that share an interval. The insertion-sort article linked above explains one simple local method; the implementation below instead uses the C++ standard library’s sort function.

Bucket Sort Example

Use ten equal intervals over [0, 1), so the index is floor(10 * x). The intervals are [0.0, 0.1), [0.1, 0.2), and so on through [0.9, 1.0). In particular, 0.1 is placed in bucket 1 because the left endpoint belongs to that interval.

For the input (0.22, 0.33, 0.1, 0.45, 0.38, 0.55, 0.21, 0.31), distribution gives:

After sorting each bucket, bucket 2 contains 0.21, 0.22 and bucket 3 contains 0.31, 0.33, 0.38; the other nonempty buckets each contain one value. Concatenating from bucket 0 through bucket 9 gives (0.1, 0.21, 0.22, 0.31, 0.33, 0.38, 0.45, 0.55) in ascending order.

Bucket Sort Algorithm Implementation

This C++ program uses the same eight values shown above. It places them into ten buckets, sorts each bucket, and prints the collected sequence.

#include <algorithm>
#include <cstddef>
#include <iostream>
#include <vector>

std::vector<double> bucketSort(const std::vector<double>& values,
                               std::size_t bucketCount) {
    std::vector<std::vector<double>> buckets(bucketCount);

    for (double value : values) {
        const std::size_t index = static_cast<std::size_t>(value * bucketCount);
        buckets[index].push_back(value);
    }

    std::vector<double> result;
    result.reserve(values.size());
    for (auto& bucket : buckets) {
        std::sort(bucket.begin(), bucket.end());
        result.insert(result.end(), bucket.begin(), bucket.end());
    }
    return result;
}

int main() {
    const std::vector<double> values = {0.22, 0.33, 0.1, 0.45,
                                        0.38, 0.55, 0.21, 0.31};
    const std::vector<double> sorted = bucketSort(values, 10);

    std::cout << "Sorted values:";
    for (double value : sorted) {
        std::cout << ' ' << value;
    }
    std::cout << '\n';
    return 0;
}

Sorted values: 0.1 0.21 0.22 0.31 0.33 0.38 0.45 0.55

The function assumes bucketCount is positive and every value is in [0, 1), which keeps the computed index inside the bucket vector. For another range, normalize values or define a mapping suited to that range before indexing. The supplied runtime evidence records a successful run of this program with exit code 0 and the sorted sequence shown above.

Bucket Sort Algorithm Complexity

Let n be the number of values, k the number of buckets, and b_j the number of values in bucket j. Creating buckets and distributing values takes O(n + k) time. With a comparison sort such as std::sort in each bucket, the additional work is bounded by the sum of the local sorting costs, O(Σ b_j log b_j); a single crowded bucket can therefore make the total O(n log n). Expected near-linear behavior is possible when values are distributed so that bucket sizes remain small, commonly with k proportional to n and an approximately uniform input distribution. It is not guaranteed by the algorithm name alone.

If insertion sort is used within buckets, a bucket of size b_j can take O(b_j²) time in the worst case. A crowded bucket can then make the total time quadratic. This is why the local sorting choice and the input distribution both matter when estimating performance.

The auxiliary space is O(n + k): the buckets store the n values and the bucket structure itself has k entries. This is the space used by the implementation, which returns a separate sorted vector. It is not O(n * k) because each value is stored in one bucket rather than copied into every bucket.