Bucket Sort

A distribution sort that distributes elements into buckets based on value range, sorts each bucket individually using insertion sort, then concatenates the results.

Algorithm Information

Time Complexity

Best: O(n+k)
Average: O(n+k)
Worst: O(n²)

Space Complexity

O(n+k)

Properties

• Distribution-based sorting
• Stable (with stable sub-sort)
• Linear time for uniform distribution
• Not in-place
1/20
Speed: 1x

Algorithm Code

1function bucketSort(arr) {
2  const n = arr.length;
3  if (n <= 1) return arr;
4 
5  const min = Math.min(...arr);
6  const max = Math.max(...arr);
7  const bucketCount = Math.ceil(Math.sqrt(n));
8  const range = (max - min + 1) / bucketCount;
9 
10  // Create empty buckets
11  const buckets = Array.from({ length: bucketCount }, () => []);
12 
13  // Distribute elements into buckets
14  for (let i = 0; i < n; i++) {
15    const idx = Math.floor((arr[i] - min) / range);
16    const bucketIdx = Math.min(idx, bucketCount - 1);
17    buckets[bucketIdx].push(arr[i]);
18  }
19 
20  // Sort each bucket with insertion sort
21  for (let i = 0; i < bucketCount; i++) {
22    insertionSort(buckets[i]);
23  }
24 
25  // Concatenate buckets back into array
26  let pos = 0;
27  for (const bucket of buckets) {
28    for (const val of bucket) {
29      arr[pos++] = val;
30    }
31  }
32 
33  return arr;
34}

Variable State

n:7
min:11
max:90
bucketCount:3
range:26.67

Call Stack

bucketSort

Array Visualization

Watch how Bucket Sort processes the array step by step

64
0
34
1
25
2
12
3
22
4
11
5
90
6

Statistics

Comparisons0
Swaps0
Step1 / 20

Legend

Comparing
Active / Swapping
Sorted
Unsorted

Starting bucket sort algorithm

How Bucket Sort Works

Learn the fundamentals of bucket sort through step-by-step explanations, code examples, and key concepts.