Bucket Sort divides input domain into buckets, places each element into its bucket, sorts each bucket (often with insertion sort), then concatenates buckets in order. It is linear on average for uniformly distributed input.
vector<double> bucketSort(vector<double> arr) {
int n = arr.size();
vector<vector<double>> b(n);
for (double x : arr) {
int idx = min(n - 1, (int)(x * n));
b[idx].push_back(x);
}
for (auto& bk : b) sort(bk.begin(), bk.end());
vector<double> out;
for (auto& bk : b) for (double x : bk) out.push_back(x);
return out;
}Map each element into one of k domain buckets.
Sort each bucket independently; small buckets are cheap.
Uniform distributions give near-linear behavior; skew can degrade performance.
Quiz coming soon for this algorithm.