Bucket Sort
Distribute elements into buckets, sort each bucket, then concatenate.
How it works
Bucket Sort partitions the input into a fixed number of equally-sized buckets based on value ranges, sorts each bucket independently (typically with insertion sort), and then concatenates the buckets to form the sorted output. When the input values are uniformly distributed, each bucket holds approximately one element on average, making the expected total work O(n).
The algorithm achieves O(n + k) average-case performance where k is the number of buckets, but degrades to O(n²) in the worst case when all elements land in a single bucket. Choosing a bucket count equal to the input size and assuming uniform distribution gives the best theoretical performance. The actual speed is highly dependent on the distribution of the data — Bucket Sort shines on uniformly distributed floating-point values but performs poorly on clustered or adversarial inputs.
Bucket Sort is stable as long as the per-bucket sort is stable (insertion sort is). It is not in-place because it requires O(n + k) auxiliary space for the bucket arrays. Its primary advantage over comparison-based sorts is that for the right data distribution it runs in linear time, rivalling Counting Sort without the constraint of integer-only input.
Complexity
Visualizer
Where it's used in the real world
Floating-point sorting in scientific computing
Uniformly distributed floats sort in O(n)Monte Carlo simulations and physics engines often produce uniformly distributed floating-point outputs that must be sorted for statistical analysis or rendering. Bucket Sort's expected O(n) time on uniform data makes it dramatically faster than O(n log n) comparison sorts for these workloads.
Histogram equalisation in image processing
Pixel values distributed into intensity bucketsHistogram equalisation maps each pixel's intensity to a target distribution. Bucket Sort naturally produces the frequency histogram as a by-product of distribution, and the sorted buckets directly yield the cumulative distribution function needed to compute the equalisation mapping.
Geographic data partitioning
GPS coordinates bucketed by latitude/longitude zonesGeospatial databases partition coordinates into spatial grid cells (buckets) for efficient range queries and nearest-neighbour lookups. Bucket Sort's distribution step maps directly onto this partitioning, enabling bulk loading of spatial indices in linear time when coordinate values are uniformly distributed across the globe.
Implementation
function bucketSort(arr: number[]): number[] {
const n = arr.length;
if (n <= 1) return [...arr];
const max = Math.max(...arr);
const buckets: number[][] = Array.from({ length: n }, () => []);
// Distribute
for (const val of arr) {
const b = Math.min(Math.floor((val / (max + 1)) * n), n - 1);
buckets[b].push(val);
}
// Sort each bucket with insertion sort
for (const bucket of buckets) {
for (let i = 1; i < bucket.length; i++) {
const key = bucket[i];
let j = i - 1;
while (j >= 0 && bucket[j] > key) {
bucket[j + 1] = bucket[j];
j--;
}
bucket[j + 1] = key;
}
}
// Concatenate
return ([] as number[]).concat(...buckets);
}
// Usage
console.log(bucketSort([29, 25, 3, 49, 9, 37, 21, 43]));
// [3, 9, 21, 25, 29, 37, 43, 49]