Bucket sort, or bin sort, is a sorting algorithm that works by distributing the elements of an array into a number of buckets. Each bucket is then sorted individually, either using a different sorting algorithm, or by recursively applying the bucket sorting algorithm.

Complexity

  • Time: worst $O(n^2)$, best $O(n+k)$, average $O(n+k)$ where $n$ is the number of buckets and $k$ is the range of the input
  • Space: worst $O(n\cdot\,k)$

Implementations

  • 1

    # TODO: Implement in Python

  • 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

    // define input variables
const N = 25; // the size of an array
const K = 5; // the number of buckets
const array = Randomize.Array1D({ N, value: () => Randomize.Integer({ min: 0, max: 999 }) });

(function main() {
  // create K buckets
  const buckets = [...new Array(K)].map(() => []);

  // find the maximum value that will be used for distribution
  const max = Math.max(...array);

  // distribute the elements into the buckets
  for (let i = 0; i < N; i++) {
    const number = array[i];
    const bucketIndex = Math.floor(number / (max + 1) * K);
    const bucket = buckets[bucketIndex];
    bucket.push(number);

    // insertion sort within the bucket
    let j = bucket.length - 1;
    while (j > 0 && bucket[j - 1] > bucket[j]) {
      const temp = bucket[j - 1];
      bucket[j - 1] = bucket[j];
      bucket[j] = temp;
      
      j--;
    }
    
  }

  // concatenate the buckets back into the array
  let i = 0;
  for (let bucketIndex = 0; bucketIndex < K; bucketIndex++) {
    const bucket = buckets[bucketIndex];
    for (let j = 0; j < bucket.length; j++) {
      array[i] = bucket[j];
      
      i++;
    }
  }
})();

References