Bucket Sort Algorithm

Previous | Home

A bucket sort begins with a single-subscripted array of positive integers to be sorted, and a double-subscripted array of integers with rows subscripted from 0 to 9 and columns subscripted from 0 to n - 1 where n is the number of values in the array to be sorted. Each row of the double-subscripted array is referred to as a bucket.

The following steps are taken for sorting the array:-

  1. Place each value of the single-subscripted array into a row of the bucket array based on the value's ones digit. For example, 97 is placed in row 7, 3 is placed in row 3 and 100 is placed in row 0. This is called a "distribution pass".
  2. Loop through the bucket array row-by-row and copy the values back to the original array. This is called the "gathering pass". The new order of the preceding values in the single-subscripted array is 100, 3 and 97.
  3. Repeat this process for each subsequent digit position (tens, hundreds, thousands, etc.).

On the second pass, 100 is placed in row 0, 3 is placed in row 0 (because 3 has no tens digit), and 97 is placed in row 9. After the gathering pass, the order of the values in the single-subscripted array is 100, 3 and 97. On the third pass, 100 is placed in row 1, 3 is placed in row 0 and 97 is placed in row 0 (after 3). After the last gathering pass, the original array is in sorted order.

Note that the double-subscripted array of buckets is ten times the size of the integer array being sorted. This sorting technique provides better performance than a bubble sort, but requires much more memory. This is an example of space-time trade-off. This version of the bucket sort requires copying all the data back to the original array on each pass. Another possibility is to create a second double-subscripted bucket array and repeatedly swap the data between the two bucket arrays.

Previous | Home

1