Bucket Sort Algorithm
Bucket Sort is a distribution-based sorting algorithm that partitions elements into ordered buckets, sorts each bucket individually, and concatenates them for O(n + k) average time.
Difficulty: Medium · Interactive Visualizer · C++ / Python / Java / JS Code
Bucket Sort Algorithm
Bucket Sort is a distribution-based sorting algorithm that divides the input range into $k$ ordered buckets, scatters each element into its corresponding bucket, sorts each bucket individually (typically with Insertion Sort), and concatenates the buckets in order. When the input is uniformly distributed, each bucket holds only $O(1)$ elements on average, giving linear $O(n + k)$ expected time.
At a Glance
| Property | Value |
| :--- | :--- |
| Best-Case Time | $O(n + k)$ (uniform distribution) |
| Average-Case Time | $O(n + k)$ (uniform distribution) |
| Worst-Case Time | $O(n^2)$ (all elements fall into one bucket sorted by Insertion Sort) |
| Auxiliary Space | $O(n + k)$ |
| In-Place? | No |
| Stable? | Yes (if elements are appended in order and each bucket uses a stable sort) |
| Comparison-Based? | Hybrid (distribution + comparison inside buckets) |
| Best Used When | Floating-point values or continuous data uniformly distributed over a known range |
---
How It Works
1. Create $k$ empty buckets (commonly $k = n$).
2. Scatter: Map each element x to a bucket index (e.g., floor(n * x) for $x \in [0, 1)$, or floor((x - min) / width) for general ranges).
3. Sort Each Bucket: Sort every non-empty bucket (Insertion Sort is ideal because buckets are small).
4. Gather: Concatenate all buckets in order back into the original array.
procedure bucketSort(A):
n = length(A)
buckets = array of n empty lists
for x in A:
idx = floor(n * x) // for x in [0, 1)
buckets[idx].append(x)
for b in buckets:
insertionSort(b)
return concatenate(buckets)
Step-by-Step Trace
Sorting [0.42, 0.32, 0.23, 0.52, 0.25, 0.47] with $n = 6$ buckets (idx = floor(6 * x)):
- Scatter:
Bucket 0:[]Bucket 1:[0.23, 0.25, 0.32]Bucket 2:[0.42, 0.47]Bucket 3:[0.52]Bucket 4–5:[]- Sort each bucket:
Bucket 1→[0.23, 0.25, 0.32],Bucket 2→[0.42, 0.47],Bucket 3→[0.52] - Gather:
[0.23, 0.25, 0.32, 0.42, 0.47, 0.52]
---
Complexity & Key Insights
- Why Uniform Distribution Matters: If all $n$ elements cluster into a single bucket, Bucket Sort degrades to the runtime of the inner bucket sort ($O(n^2)$ for Insertion Sort, or $O(n \log n)$ if you use
std::sort/ Merge Sort). - Bucket Sort vs. Counting Sort: Counting Sort assigns one counter per exact integer key; Bucket Sort assigns one container per interval of values, so it naturally handles floating-point numbers and arbitrary real intervals.
- Pigeonhole Principle Trick: Several classic $O(n)$ interview problems (like Maximum Gap and Contains Duplicate III) use Bucket Sort's bucketing idea without ever sorting the buckets—tracking only each bucket's
minandmax.
---
Practice Problems
Easy
1. Sort Floating-Point Numbers in $[0, 1)$
Given an array of floating-point numbers in $[0, 1)$, sort them using Bucket Sort with Insertion Sort inside each bucket.
Approach: Place each x into bucket min(n - 1, int(n * x)), run Insertion Sort on each bucket, and concatenate. Time: $O(n)$ average / $O(n^2)$ worst. Space: $O(n)$.
<details>
<summary>Show C++ Solution</summary>
#include <algorithm>
#include <iostream>
#include <vector>
void insertionSort(std::vector<double>& bucket) {
for (int i = 1; i < static_cast<int>(bucket.size()); ++i) {
double key = bucket[i];
int j = i - 1;
while (j >= 0 && bucket[j] > key) {
bucket[j + 1] = bucket[j];
--j;
}
bucket[j + 1] = key;
}
}
void bucketSort(std::vector<double>& arr) {
int n = static_cast<int>(arr.size());
if (n <= 1) return;
std::vector<std::vector<double>> buckets(n);
for (double x : arr) {
int idx = std::min(n - 1, static_cast<int>(n * x));
buckets[idx].push_back(x);
}
int pos = 0;
for (auto& b : buckets) {
insertionSort(b);
for (double x : b) {
arr[pos++] = x;
}
}
}
int main() {
std::vector<double> data = {0.42, 0.32, 0.23, 0.52, 0.25, 0.47};
bucketSort(data);
for (double x : data) std::cout << x << " ";
std::cout << "\n";
return 0;
}
</details>
2. Sort Characters by Frequency (LeetCode 451)
Given a string s, sort its characters in decreasing order of frequency in $O(n)$ time.
Approach: Count character frequencies, then place each character into buckets[freq]. Because frequencies are bounded by s.size(), scanning buckets from n down to 1 produces the answer in linear time. Time: $O(n)$. Space: $O(n)$.
<details>
<summary>Show C++ Solution</summary>
#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>
std::string frequencySort(const std::string& s) {
std::unordered_map<char, int> freq;
for (char c : s) ++freq[c];
int n = static_cast<int>(s.size());
std::vector<std::vector<char>> buckets(n + 1);
for (const auto& [ch, count] : freq) {
buckets[count].push_back(ch);
}
std::string result;
result.reserve(n);
for (int f = n; f >= 1; --f) {
for (char ch : buckets[f]) {
result.append(f, ch);
}
}
return result;
}
int main() {
std::cout << frequencySort("tree") << "\n";
return 0;
}
</details>
---
Intermediate
3. Maximum Gap (LeetCode 164)
Given an unsorted integer array, find the maximum difference between two successive elements in its sorted form in $O(n)$ time and $O(n)$ space.
Approach: By the pigeonhole principle, the maximum gap is at least $\lceil (\text{max} - \text{min}) / (n - 1) \rceil$. Set bucketSize = max(1, (max - min) / (n - 1)). Then two numbers in the same bucket can never form the maximum gap! Track only min and max per bucket, and compute bucket[i].min - prevBucket.max across non-empty buckets. Time: $O(n)$. Space: $O(n)$.
<details>
<summary>Show C++ Solution</summary>
#include <algorithm>
#include <climits>
#include <iostream>
#include <vector>
int maximumGap(const std::vector<int>& nums) {
int n = static_cast<int>(nums.size());
if (n < 2) return 0;
auto [minIt, maxIt] = std::minmax_element(nums.begin(), nums.end());
int mn = *minIt, mx = *maxIt;
if (mn == mx) return 0;
int bucketSize = std::max(1, (mx - mn) / (n - 1));
int bucketCount = (mx - mn) / bucketSize + 1;
struct Bucket {
int mn = INT_MAX;
int mx = INT_MIN;
bool used = false;
};
std::vector<Bucket> buckets(bucketCount);
for (int x : nums) {
int bi = (x - mn) / bucketSize;
buckets[bi].used = true;
buckets[bi].mn = std::min(buckets[bi].mn, x);
buckets[bi].mx = std::max(buckets[bi].mx, x);
}
int prevMax = mn;
int maxGap = 0;
for (const auto& b : buckets) {
if (!b.used) continue;
maxGap = std::max(maxGap, b.mn - prevMax);
prevMax = b.mx;
}
return maxGap;
}
int main() {
std::vector<int> data = {3, 6, 9, 1};
std::cout << "Maximum gap: " << maximumGap(data) << "\n";
return 0;
}
</details>
4. Contains Duplicate III (LeetCode 220)
Given an array nums and integers k and t, determine whether there exist distinct indices i and j such that $|i - j| \le k$ and $|\text{nums}[i] - \text{nums}[j]| \le t$.
Approach: Partition values into buckets of width $w = t + 1$ inside a sliding window of size $k$. Any two values within $t$ of each other must either fall into the same bucket or immediately adjacent buckets (bi - 1 or bi + 1). Checking those three buckets takes $O(1)$ per element. Time: $O(n)$. Space: $O(\min(n, k))$.
<details>
<summary>Show C++ Solution</summary>
#include <cstdlib>
#include <iostream>
#include <unordered_map>
#include <vector>
bool containsNearbyAlmostDuplicate(const std::vector<long long>& nums, int k, long long t) {
if (k <= 0 || t < 0) return false;
std::unordered_map<long long, long long> buckets;
long long w = t + 1;
auto getBucketId = [w](long long x) {
return x >= 0 ? x / w : (x + 1) / w - 1;
};
for (int i = 0; i < static_cast<int>(nums.size()); ++i) {
long long x = nums[i];
long long bi = getBucketId(x);
if (buckets.count(bi)) return true;
if (buckets.count(bi - 1) && std::llabs(x - buckets[bi - 1]) <= t) return true;
if (buckets.count(bi + 1) && std::llabs(x - buckets[bi + 1]) <= t) return true;
buckets[bi] = x;
if (i >= k) {
buckets.erase(getBucketId(nums[i - k]));
}
}
return false;
}
int main() {
std::vector<long long> data = {1, 2, 3, 1};
std::cout << std::boolalpha << containsNearbyAlmostDuplicate(data, 3, 0) << "\n";
return 0;
}
</details>
---
Hard
5. Sort Arbitrary Real Numbers with Dynamic Range Bucketing
Sort an array of arbitrary floating-point numbers (including negatives and values outside $[0, 1)$) using Bucket Sort.
Approach: Compute minVal and maxVal, normalize each value into $[0, 1)$ via (x - minVal) / (maxVal - minVal), map it into n buckets (clamping the maximum to bucket n - 1), sort each bucket with Insertion Sort, and concatenate. Time: $O(n)$ average for uniform distributions. Space: $O(n)$.
<details>
<summary>Show C++ Solution</summary>
#include <algorithm>
#include <iostream>
#include <vector>
void insertionSort(std::vector<double>& bucket) {
for (int i = 1; i < static_cast<int>(bucket.size()); ++i) {
double key = bucket[i];
int j = i - 1;
while (j >= 0 && bucket[j] > key) {
bucket[j + 1] = bucket[j];
--j;
}
bucket[j + 1] = key;
}
}
void bucketSortGeneral(std::vector<double>& arr) {
int n = static_cast<int>(arr.size());
if (n <= 1) return;
auto [minIt, maxIt] = std::minmax_element(arr.begin(), arr.end());
double mn = *minIt, mx = *maxIt;
if (mn == mx) return;
std::vector<std::vector<double>> buckets(n);
double span = mx - mn;
for (double x : arr) {
int idx = static_cast<int>(((x - mn) / span) * (n - 1));
idx = std::clamp(idx, 0, n - 1);
buckets[idx].push_back(x);
}
int pos = 0;
for (auto& b : buckets) {
insertionSort(b);
for (double x : b) arr[pos++] = x;
}
}
int main() {
std::vector<double> data = {-12.5, 3.1, 0.0, -2.4, 15.8, 7.2, -12.5};
bucketSortGeneral(data);
for (double x : data) std::cout << x << " ";
std::cout << "\n";
return 0;
}
</details>
---
Related Algorithms
- Counting Sort — special case of Bucket Sort where each bucket represents a single integer key.
- Radix Sort — multi-pass bucketing by digit for large integer ranges.
- Insertion Sort — commonly used to sort individual buckets.