Skip to content

Bucket Sort

This page gives a brief introduction to bucket sort.

Definition

Bucket sort is a sorting algorithm that works well when the data to be sorted has a large value range but is fairly uniformly distributed.

Procedure

Bucket sort proceeds in the following steps:

  1. Set up a fixed number of arrays to serve as empty buckets;
  2. Go through the sequence and put the elements one by one into their buckets;
  3. Sort every non-empty bucket;
  4. Put the elements from the non-empty buckets back into the original sequence.

Properties

Stability

If the inner sort is stable and inserting the elements into the buckets does not change their relative order, then bucket sort is a stable sorting algorithm.

Each block holds only a few elements, so insertion sort is the usual choice. Bucket sort is then a stable sorting algorithm.

Time complexity

Let \(n\) be the number of elements and \(k\) the number of buckets. If the elements fall into the buckets independently and uniformly, the average-case time complexity of bucket sort is \(O(n + n^2/k + k)\) (splitting the value range evenly into \(k\) blocks + sorting + merging the elements back together), which is \(O(n)\) when \(k\approx n\).1

The worst-case time complexity of bucket sort is \(O(n^2+k)\).

Implementation

Below, a[] is indexed from \(1\), and we require \(0\le a_i\le w\) and \(0\le n<N\), where \(w\) is an upper bound on the largest key.

 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
constexpr int N = 100010;

int n, w, a[N];
vector<int> bucket[N];

void insertion_sort(vector<int>& A) {
  for (int i = 1; i < A.size(); ++i) {
    int key = A[i];
    int j = i - 1;
    while (j >= 0 && A[j] > key) {
      A[j + 1] = A[j];
      --j;
    }
    A[j + 1] = key;
  }
}

void bucket_sort() {
  if (n == 0) return;
  auto bucket_size = unsigned(w / n) + 1;
  for (int i = 0; i < n; ++i) {
    bucket[i].clear();
  }
  for (int i = 1; i <= n; ++i) {
    bucket[a[i] / bucket_size].push_back(a[i]);
  }
  int p = 0;
  for (int i = 0; i < n; ++i) {
    insertion_sort(bucket[i]);
    for (int j = 0; j < bucket[i].size(); ++j) {
      a[++p] = bucket[i][j];
    }
  }
}
 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
N = 100010
w = n = 0
a = [0] * N
bucket = [[] for i in range(N)]


def insertion_sort(A):
    for i in range(1, len(A)):
        key = A[i]
        j = i - 1
        while j >= 0 and A[j] > key:
            A[j + 1] = A[j]
            j -= 1
        A[j + 1] = key


def bucket_sort():
    if n == 0:
        return
    bucket_size = w // n + 1
    for i in range(0, n):
        bucket[i].clear()
    for i in range(1, n + 1):
        bucket[a[i] // bucket_size].append(a[i])
    p = 0
    for i in range(0, n):
        insertion_sort(bucket[i])
        for j in range(0, len(bucket[i])):
            p += 1
            a[p] = bucket[i][j]

References and notes