Bucket Sort

Distributes elements into buckets, sorts each bucket, then concatenates them.

Best: O(n + k) · Avg: O(n + k) · Worst: O(n²) · Space: O(n + k)

72
44
23
61
10
45
47
69
29
66
93
94
70
98
68
Speed5
Size15
TypeScript
function bucketSort(arr: number[]): number[] {
  const min = Math.min(...arr), max = Math.max(...arr);
  const n = arr.length, buckets = Math.sqrt(n);
  const bucketSize = (max - min + 1) / buckets;
  const bucket: number[][] = Array.from({ length: buckets }, () => []);
  for (let x of arr) {
    const idx = Math.min(buckets - 1, Math.floor((x - min) / bucketSize));
    bucket[idx].push(x);
  }
  bucket.forEach(b => b.sort((a, c) => a - c));
  return bucket.flat();
}