Sorting / Distribution Bucket Sort Medium

Bucket Sort — Distribute, Sort, Concatenate

Split elements into range-based buckets, sort each individually, then merge. O(N+K) average time.

GFG
Practice this algorithm on GeeksforGeeks to reinforce your understanding.
Open Problem

What does it solve?

Sorts an array by distributing elements into buckets based on value ranges. Each bucket is sorted individually (often with insertion sort), then all buckets are concatenated to produce the final sorted array.

Key insight: if input is uniformly distributed, each bucket gets roughly the same number of elements, making inner sorts fast. This gives O(N + K) average time.

The Formula

// Compute bucket index for each element
bucketIdx = floor((val - min) / bucketRange)
// where bucketRange = (max - min + 1) / numBuckets

// Three phases:
1. Distribute into buckets
2. Sort each bucket
3. Concatenate all buckets
Interactive Visualization — Bucket Sort
Current element Placed in bucket Sorted / Done
Input Array
Output Array
Phase
—
Step
0
Comparisons
0
Sorted
0
Click Play or Step to begin the bucket sort animation.
Speed5x
C++ — Bucket Sort
void bucketSort(vector<float>& arr) {
    int n = arr.size();
    vector<vector<float>> buckets(n);

    // Phase 1: Distribute into buckets
    for (int i = 0; i < n; i++) {
        int idx = n * arr[i]; // for [0,1) range
        buckets[idx].push_back(arr[i]);
    }

    // Phase 2: Sort individual buckets
    for (int i = 0; i < n; i++)
        sort(buckets[i].begin(), buckets[i].end());

    // Phase 3: Concatenate
    int idx = 0;
    for (auto& bucket : buckets)
        for (float val : bucket)
            arr[idx++] = val;
}
Complexity
Average Time
O(N + K)

N elements, K buckets. Uniform distribution assumed.

Worst Time
O(N²)

All elements in one bucket: degrades to inner sort.

Space
O(N + K)

Extra space for K buckets holding N elements.

Stable?
Yes

Preserves relative order within each bucket.

📝 Notes

▼