Bucket Sort

Range-based distribution sorting

Bucket Sort works by distributing elements into several buckets. Each bucket is then sorted individually, often using another sorting algorithm like Insertion Sort, and finally concatenated to form the sorted array.

Phase

Ready

Buckets

5 Ranges

Elements [0.0 - 1.0]

Range Buckets

[0.0, 0.2)

Bucket 0

[0.2, 0.4)

Bucket 1

[0.4, 0.6)

Bucket 2

[0.6, 0.8)

Bucket 3

[0.8, 1.0)

Bucket 4

Press "Start Sorting" to begin

Core Mechanics

Bucket sort is a scatter-gather algorithm. It works best when the input is uniformly distributed over a range, such as $[0, 1)$.

uniform distribution

Performance hinges on elements being spread evenly. If many elements fall into one bucket, it reverts to the performance of the inner sort.

Inner Sort

Typically, Insertion Sort is used for buckets because they are expected to be small, where insertion sort is very efficient.

Performance

Expected Time$O(n + k)$

Worst Case$O(n^2)$

Stable?Yes

In-Place?No

Bucketing Logic

Pseudocode

JavaScript

1// n = elements, k = buckets
2index = floor(n * array[i])
3buckets[index].push(array[i])
4 
5for bucket in buckets:
6  sort(bucket)
7 
8return concatenate(buckets)

Implementations

Python Implementation

Pseudocode

Python

1def bucket_sort(arr):
2    n = len(arr)
3    buckets = [[] for _ in range(n)]
4    
5    for x in arr:
6        index = int(n * x)
7        buckets[index].append(x)
8        
9    for i in range(n):
10        buckets[i].sort() # usually insertion sort
11        
12    res = []
13    for b in buckets:
14        res.extend(b)
15    return res

JavaScript Implementation

Pseudocode

JavaScript

1function bucketSort(arr) {
2  let n = arr.length;
3  let buckets = Array.from({ length: n }, () => []);
4  
5  for (let x of arr) {
6    let i = Math.floor(n * x);
7    buckets[i].push(x);
8  }
9  
10  for (let b of buckets) {
11    b.sort((a, b) => a - b);
12  }
13  
14  return [].concat(...buckets);
15}

Core Mechanics

Bucket sort is a scatter-gather algorithm. It works best when the input is uniformly distributed over a range, such as $[0, 1)$.

uniform distribution

Performance hinges on elements being spread evenly. If many elements fall into one bucket, it reverts to the performance of the inner sort.

Inner Sort

Typically, Insertion Sort is used for buckets because they are expected to be small, where insertion sort is very efficient.

Implementations

Python Implementation

Pseudocode

Python

1def bucket_sort(arr):
2    n = len(arr)
3    buckets = [[] for _ in range(n)]
4    
5    for x in arr:
6        index = int(n * x)
7        buckets[index].append(x)
8        
9    for i in range(n):
10        buckets[i].sort() # usually insertion sort
11        
12    res = []
13    for b in buckets:
14        res.extend(b)
15    return res

JavaScript Implementation

Pseudocode

JavaScript

1function bucketSort(arr) {
2  let n = arr.length;
3  let buckets = Array.from({ length: n }, () => []);
4  
5  for (let x of arr) {
6    let i = Math.floor(n * x);
7    buckets[i].push(x);
8  }
9  
10  for (let b of buckets) {
11    b.sort((a, b) => a - b);
12  }
13  
14  return [].concat(...buckets);
15}