Bucket Sort Algorithm

Bucket sort is a non-comparison based sorting algorithm helpful in scenarios where your data to be sorted is uniformly distributed over a particular range.

Let’s say we are having an array with n elements. And all the elements in the range 0 to m-1.

Example: input arr: [23,15,21,9,2,10], here the range of elements is 0 to 23. So, n=6, m=24

To sort this array using bucket sort, we have to take the help of n buckets. Each bucket can store a list of elements from input array.

Note: here the Number of buckets we have taken is equal to the size of input array

Initially our buckets are empty.

Step 1: For each number in the input array, insert it to the appropriate bucket. Time complexity: O(n)

for(i=0; i<n; i++){
    insert arr[i] to the bucket floor(n*arr[i]/m)
}

arr[i] will get mapped to the bucket floor(n*arr[i]/m)

So, our input array elements will get mapped to their appropriate buckets like this:

Element 23 will get mapped to floor(6*23/24). Element 15 will get mapped to the bucket floor( 6*15/24 ) and so on….

Mapping of elements in the input arr to their appropriate buckets

Input arr elements inserted to their appropriate buckets

Step 2: Sort every bucket separately using insertion sort.

After sorting each bucket using insertion sort

For Step 2, best case will happen if the numbers in the input array are uniformly distributed within the range (0 to m-1). In that case every bucket will have only one element. Then insertion sort will take only O(1) to sort every bucket. Therefor to sort n buckets it will take O(n).

For step 2, worst case will happen if the numbers in the input array are not uniformly distributed, then all the elements of input array might get mapped to a single bucket. Therefore in worst case, insertion sort for sorting n elements in a bucket might take up to O(n²).

Therefore, we use bucket sort only in the case when numbers in the input array are uniformly distributed over a range.

Step 3: Traverse all the buckets from top to down and output all the numbers in the sorted buckets.

for all buckets i=0 to n-1
{
    for every number in bucket i
    {
        add number to output array
    }
}

Time complexity Analysis

Time complexity of bucket sort is O(n), when the numbers in the input array are uniformly distributed over a particular range. O(n) for step 1 +O(n) for step 2 +O(n) for step 3.

Time complexity of bucket sort is O(n²), when the numbers are not uniformly distributed over a particular range. O(n) for step 1+ O(n²) for step 2+ O(n) for step 3.

Best Case Time Complexity: O(n), Average Case Time Complexity: O(n), Worst Case Time Complexity: O(n²)