Bucket Sort: Mechanism, Complexity Analysis & Interactive Visualizer

Bucket Sort

A distribution-based sorting algorithm that partitions elements into a finite number of buckets, sorts each bucket individually (using Insertion Sort), and then merges them.

How it works

Bucket Sort works by dividing the interval of input values into equal-sized sub-intervals (buckets). Each input value is placed into its corresponding bucket, sorted, and then gathered sequentially.

1. Create an array of empty buckets.
2. Distribute the elements from the input array into the buckets based on their values relative to the range (minimum and maximum).
3. Sort each non-empty bucket using a simple sorting algorithm like Insertion Sort.
4. Visit all buckets in order and copy their sorted elements back into the original array.

Complexity

Interactive visualization

Pseudocode

procedure bucketSort(A):
  n ← length(A)
  min, max ← findMinMax(A)
  numBuckets ← floor(n / 2)
  buckets ← array of numBuckets empty lists
  range ← max - min
  
  for i from 0 to n - 1:
    bucketIdx ← floor(((A[i] - min) / range) * (numBuckets - 1))
    buckets[bucketIdx].append(A[i])
    
  idx ← 0
  for i from 0 to numBuckets - 1:
    insertionSort(buckets[i])
    for j from 0 to length(buckets[i]) - 1:
      A[idx] ← buckets[i][j]
      idx ← idx + 1

JavaScript implementation

function bucketSort(arr) {
  const n = arr.length;
  if (n <= 1) return arr;

  let min = arr[0];
  let max = arr[0];
  for (let i = 1; i < n; i++) {
    if (arr[i] < min) min = arr[i];
    if (arr[i] > max) max = arr[i];
  }

  if (min === max) return arr;

  const numBuckets = Math.max(2, Math.floor(n / 2));
  const buckets = Array.from({ length: numBuckets }, () => []);
  const range = max - min;

  for (let i = 0; i < n; i++) {
    const bucketIdx = Math.floor(((arr[i] - min) / range) * (numBuckets - 1));
    buckets[bucketIdx].push(arr[i]);
  }

  let idx = 0;
  for (let i = 0; i < numBuckets; i++) {
    insertionSort(buckets[i]);
    for (let j = 0; j < buckets[i].length; j++) {
      arr[idx++] = buckets[i][j];
    }
  }
  return arr;
}

function insertionSort(arr) {
  const len = arr.length;
  for (let i = 1; i < len; i++) {
    const key = arr[i];
    let j = i - 1;
    while (j >= 0 && arr[j] > key) {
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = key;
  }
}

Pros and cons

When to use it

• Uniformly Distributed Data: when elements are evenly spread over an interval (such as percentage values or decimal probabilities).
• Float Sorting: ideal for sorting floats in the range [0, 1).