Speed:

Bucket Sort

Time: O(n + k)Space: O(n + k)Stable (if stable sort used in buckets)

🪣How Bucket Sort Works

Bucket Sort distributes the elements of an array into a number of buckets. Each bucket is then sorted individually, either using a different sorting algorithm or recursively applying bucket sort.

It is especially effective when input is uniformly distributed over a range. The overall process is:

Divide the interval [min, max] into k buckets.
Scatter the input elements into the buckets.
Sort each bucket (often with insertion sort).
Concatenate all buckets to get the sorted array.

💻Implementation

// Bucket Sort (for numbers in [0, 1))
function bucketSort(arr) {
  const n = arr.length;
  const buckets = Array.from({ length: n }, () => []);
  // 1. Scatter: Place elements in buckets
  for (let i = 0; i < n; i++) {
    const idx = Math.floor(n * arr[i]);
    buckets[idx].push(arr[i]);
  }
  // 2. Sort each bucket
  for (let i = 0; i < n; i++) {
    buckets[i].sort((a, b) => a - b);
  }
  // 3. Gather: Concatenate buckets
  return [].concat(...buckets);
}

📏Key Properties & Insights

Bucket Index Formula

index = ⌊ k × (A[i] - min) / (max - min + 1) ⌋

• k = number of buckets
• min, max = range of input
• A[i] = element value

Complexity

• Best: O(n + k) (uniform distribution)
• Worst: O(n²) (all elements in one bucket)
• Space: O(n + k)
• Stable if bucket sort is stable

🔬 Applications

• Floating point sorting
• Uniformly distributed data
• Histogram-based algorithms
• External sorting (large datasets)

🧮 Tips & Insights

• Choose bucket count based on data distribution
• Use insertion sort for small buckets
• Not comparison-based: exploits distribution
• Works best for continuous, uniform data