Radix Sort vs Bucket Sort

We have two standard sorting algorithms, named bucket sort and radix sort. They both share differences and similarities. Let’s explore some similarities, differences, advantages, and disadvantages here in more detail.

Bucket Sort:

Bucket sort is a sorting algorithm in which the elements are separated into several groups that are called buckets. Each bucket is then sorted individually using any other algorithm or recursively using bucket sort itself. Then the sorted buckets are gathered together.

Bucket sort is mainly useful when input is uniformly distributed over a range.

Bucket Sort Algorithm:

The algorithm can be expressed as following:

1. Take the array then find the maximum and minimum elements of the array. Find the range of each bucket.
   Bucket range:((maximum element – minimum element)/number of elements)
2. Now insert the element into the bucket based on Bucket Index. 
   Bucket Index: floor(a[i]-minimum element)/range
3. Once the elements are inserted into each bucket, sort the elements within each bucket using the insertion sort.

Illustration:

Consider an array arr[] = {22, 72, 62, 32, 82, 142}

Range = (maximum-minimum) / number of elements
So, here the range will be given as: Range = (142 – 22)/6 = 20

Thus, the range of each bucket in bucket sort will be: 20 So, the buckets will be as:
20-40; 40-60; 60-80; 80-100; 100-120; 120-140; 140-160

Bucket index = floor((a[i]-min)/range)
For 22, bucketindex = (22-22)/20 = 0.
For 72, bucketindex = (72-22)/20 = 2.5. 
For 62, bucketindex = (62-22)/20 = 2.
For 32, bucketindex = (32-22)/20 = 0.5.
For 82, bucketindex = (82-22)/20 = 3.
For 142, bucketindex = (142-22)/20 = 6.

Elements can be inserted into the bucket as:
0 -> 22 -> 32
1
2 -> 72 -> 62 (72 will be inserted before 62 as it appears first in the list).
3 -> 82
4
5 
6 -> 142

Now sort the elements in each bucket using the insertion sort.
0 -> 22 -> 32
1
2 -> 62 -> 72
3 -> 82
4 
5
6 -> 142

Now gather them together.
arr[] = {22, 32, 62, 72, 82, 142}

Radix Sort:

The idea of Radix Sort is to do digit-by-digit sorting starting from the least significant digit to the most significant digit. Radix sort uses counting sort as a subroutine to sort.

Radix Sort Algorithm:

The algorithm can be described as follows:

1. Take the array. Check whether the number of digits in every array element is the same. If it is not the same, make it the same by using 0 before MSB.
2. Find how many buckets are needed. Now, if you are given a decimal number, the digit will fall in the range of 0 to 9, so take 10 buckets. If you are given a string, then characters will fall in the range a-z (26 alphabets), so consider 0 – 25 buckets.
3. Begin with the LSB (leftmost bit/character) and place the number based on the LSB in the appropriate bucket number. (Do not sort within the buckets). Just concatenate from the buckets and append the numbers in an empty array.
4. Once it is done with one’s place (LSB), follow step 3 again for ten’s place, the hundred’s place, and so on until the MSB is reached.
5. The last output will be the resultant sorted array.

Illustration:

Consider array arr[] = {22, 72, 62, 32, 82, 142}

We will sort based on LSB to MSB (keeping the number of digits the same in every number). The numbers will be: 
022, 072, 062, 032, 082, 142

We will have 10 buckets ranging from 0 to 9. Start from one place.

PASS 1
0
1
2 -> 022 -> 072 -> 062 -> 042 -> 032 -> 082 -> 142
3
4
5
6
7
8
9
Resulting list: {022, 072, 062, 042, 032, 082, 142}

PASS 2
0
1
2 -> 022
3 -> 032
4 -> 042 -> 142
5
6 -> 062
7 -> 072
8 -> 082
9
Resulting list: {022, 032, 042, 142, 062, 072, 082}

PASS 3
0 -> 022 -> 032 -> 042 -> 062 -> 072 -> 082
1 -> 142
2
3
4
5
6
7
8
9
Resulting list: {022, 032, 042, 062, 072, 082, 142}

Below are some major differences between Radix Sort and Bucket Sort: 

It was found that bucket sort is faster as compared to radix sort, but it uses more memory when compared to radix sort.

Advantages And Disadvantages of Radix Sort:

Advantages:

• It is fast when the numbers are small If the numbers are small, the number of passes will also be small. So, it becomes more efficient.
• It is a stable sorting algorithm, i.e., it maintains the relative order of elements with equal values.
• It is used in many suffix array construction algorithms.

Disadvantages:

• It will sometimes consume more memory than is required.
• It is based on digits or letters, so it is less flexible as compared to other sorting algorithms as one needs to know the entire data priorly only.

Advantages And Disadvantages of Bucket Sort:

Advantages:

It allows the buckets to be processed independently (you need to sort them independently within the buckets). This plays a great role in the processing of files.

Disadvantages:

• It works more efficiently when the data is either less or more evenly distributed.
• This technique is not valid for all data types due to its bucketing technique.

When to use Radix Sort vs. Bucket Sort

• Radix Sort is suitable for sorting elements with varying key sizes and for parallelization
• Bucket Sort is suitable for sorting uniformly distributed numbers within a specific range and works well with distributed computing
• Choosing the right algorithm depends on the size of the dataset, the distribution of the data, and the computing environment

Related Articles:

• Radix Sort:
• Bucket Sort