Bucket/Radix Sort

Most people use the bucket sort method when sorting a list of names in alphabetical order. The procedure is:

• First, the names are grouped according to the first letter, thus the names are arranged in 26 classes, one for each letter of the alphabet. The first class consists of those names that begin with letter A, the second class consists of those names that begin with letter B, and so on.
• Next, the names are grouped according to the second letter. After this step, the list of names will be sorted on the first two letters.
• This process is continued for a number of times equal to the length of the name with maximum letters.

Since there are 26 letters in the alphabet, we make use of 26 buckets, one for each letter of the alphabet. After grouping these names according to their specific letter, we collect them according to the order of the buckets. This new list becomes the input for the next pass when we consider the next letter.

To sort decimal numbers where the base (or radix) is 10, we need 10 buckets, numbered from 0-9. Unlike sorting names, decimal numbers are sorted from right to left i.e. first on unit digits, then on ten digits and so on.

Example

Here is an illustration of how bucket sorting works. Consider the following unsorted array:

After pass three, when the numbers are collected, they are in the following order:

Thus, the numbers are sorted.

Algorithm

Bucketsort(a,n)

Here a is a linear array of integers with n elements, the variable digitcount is used to store the number of digits in the largest number in order to control the number of passes to be performed.

Begin
    find the largest number of the array
    set digitcount=no. of digits of the largest no.
    for pass=1 to digitcount by 1 do
        initialize buckets
        for i=1 to n-1 by 1 do
            set digit=obtain digit no. pass of a[i]
            put a[i] in bucket no. digit
            increment bucket count for bucket no. digit
        endfor
        collect all the numbers from buckets in order
    endfor
end

Analysis of Bucket Sort

Suppose that the number of digits in the largest number of the given array is s and the number of passes to be performed is n. Then, the number of comparisons, f(n), needed to sort the given array are:
f(n)=n*s*10, where 10 is the decimal number base.

Though s is independent of n, but if s=n, then in worst case, f(n)=O(n²).

But on the other hand, if s=log₁₀ n, hen f(n)=O(n log₁₀ n).

From the above discussion, we conclude that bucket sort performs well only when the number of digits in the elements are very small.