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}

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.