Bucket Sort

Bucket Sort is not a general-purpose sorting algorithm. Its value does not come from guaranteeing optimal performance in all scenarios, but from exploiting specific properties of the input data.

Rather than ordering elements through comparisons, Bucket Sort approaches sorting as a distribution problem. Elements are grouped into a finite number of buckets based on a known rule, and ordering emerges naturally from the way these buckets are traversed and combined.

This shift in perspective is what makes Bucket Sort interesting. When the input data exhibits structure, such as a bounded range of values or a meaningful notion of frequency, the global sorting problem can be reduced to a collection of smaller and simpler local operations.

Algorithm

At a high level, Bucket Sort proceeds in three conceptual phases.

First, the algorithm defines a fixed number of buckets and a rule that assigns each input element to one of them. This rule depends on the constraints of the problem and encodes how values are distributed across the domain.

Second, elements are scattered into buckets according to this rule. At this stage, no global ordering is enforced. The algorithm only ensures that elements assigned to earlier buckets should appear before elements assigned to later buckets in the final result.

Finally, each bucket is processed independently, typically by applying a simple comparison-based sort. The final sorted output is obtained by concatenating the buckets in order.

The correctness of Bucket Sort relies on a single invariant: if an element belongs to bucket i and another element belongs to bucket j, with i < j, then the first element must appear before the second in the final ordering.

function bucketSort(arr: number[], bucketCount: number = 5): number[] {
  if (arr.length <= 1) return arr;

  // Determine min and max values
  const minValue = Math.min(...arr);
  const maxValue = Math.max(...arr);

  // Initialize buckets
  const buckets: number[][] = Array.from({ length: bucketCount }, () => []);

  // **** Scatter elements into buckets ****
  // Rule to distribute CAN CHANGE based on the REQUIREMENTS of the problem.
  // ----
  for (const num of arr) {
    const index = Math.floor(((num - minValue) / (maxValue - minValue + 1)) * bucketCount);
    buckets[index].push(num);
  }
  // ----

  // **** Sort individual buckets and concatenate ****
  // Sort CAN CHANGE based on the REQUIREMENTS of the problem.
  // ----
  const sortedArray: number[] = [];
  for (const bucket of buckets) {
    bucket.sort((a, b) => a - b); // using built-in sort (can use insertion sort)
    sortedArray.push(...bucket);
  }
  // ----

  return sortedArray;
}

Time and Space Complexity

The performance of Bucket Sort depends on how evenly elements are distributed across buckets.

When elements are reasonably balanced across buckets, each bucket contains only a small number of elements, and the overall time complexity approaches linear behavior. The Expected time complexity is $O(n)$, assuming uniform distribution. The Worst case: $O(n^2)$, when all elements fall into a single bucket.

Bucket Sort requires additional memory to store buckets and their contents. The expected space complexity is $O(n + k)$, where $k$ is the number of buckets.

This dependency on extra space is the primary tradeoff of the algorithm.

Exercises