This article compares counting sort, radix sort, and bucket sort with important points that will help you make out the differences between these sorting algorithms.

Table of content:

1. Basics of 3 different sorting algorithms
2. Differences between Counting Sort, Radix Sort and Bucket Sort
   2.1. Time Complexity
   2.2. How they work?
   2.3. Implementation
   2.4. Other important points

Basics of 3 different sorting algorithms

Counting Sort

Counting sort is a non comparison based linear time sorting algorithm for cases where the input elements are in a limited range, usually with a given maximum limit.

Radix Sort

Radix sort is algorithm like counting sort is a linear time sorting algorithm if your data is within a limited range.

Bucket Sort

Bucket sort is a sorting algorithm which works in linear time when the data is uniformly distributed acorss a range.

Differences between Counting Sort, Radix Sort and Bucket Sort

Time Complexity:

• The time complexity for counting sort is linear only when the range limit is linear. The time complexity is Θ(n + k) where n is the range limit and k represents the time to traverse the original array.

• Radix sort works in linear time even if the range of the data is exponential. Assuming we have d digits as our maximum.The time complexity will beΘ(d*(n + b)) where b is the base and n the is the number of elements.

• In comparison with radix sort and counting sort, bucket sort works in linear time and is the better algorithm when the data is perfectly distributed across a range. Bucket sort has a time complexity of Θ(n). Assuming k is approximately equal to n. In this case, k is the number of buckets and n is the number of items in the input array.

How they work:

• In Counting sort the count of the elements is stored in an auxiliary array and the sorting is done by mapping the count as an index of the auxiliary array.

• Radix sort first sort elements by grouping digits of the same place and subsequently sort the elements according to their required order, either by increasing or decreasing order.

• The Bucket sort algorithm first divides the unsorted array elements into groups of buckets and then sorts the elements int the bucket using a sorting algorithm of choice.

Implementation:

• Implementation of Counting sort in Java

void countSort(originalArray, originalArraySize, rangeLimit){
        int count[] = new int[rangeLimit + 1];
        int sorted[] = new int[originalArraySize.length];
        for(int i = 0; i < originalArraySize.length; i++){
            count[arr[i]]++;
        }   
        int index = 0; 
        for(int i = rangeLimit; i > =0; i--){
            int score = count[i];
          for(int j =0; j < score;j++){
            sorted[index] = i;
            index++;  
              }
        }
       
  }

• Implementation of Radix sort in Java

void radixSort(int arr[], int n){
    int max = arr[0];
    for(int i=1; i<n; i++){
        if(arr[i] > max){
            max = arr[i];
        }
    }
    for(int exp = 1; max/exp>0; exp *=10){
        countingSort(arr,n,exp);
    }
}
void countingSort(int arr[], int n, int exp){
    int []output = new int[n];
    int []count = new int[10];
    for(int i = 0; i < n; i++){
        count[(arr[i]/exp)%10]++;
        }
    for(int i=1; i < 10; i++){
        count[i] += count[i - 1];
    }
    for(int i = n-1; i >= 0; i--){
        output[count[(arr[i]/exp)%10] - 1] = arr[i];
        count[(arr[i]/exp)%10]--;
    }
    for(int i =0; i < n; i++){
        arr[i] = output[i];
    }
}

• Implementation of Bucket sort in Java

void bucketSort(int arr[], int k){
    //k is the number of buckets
    int n = arr.length;
    int max_val = arr[o];
    for(int i =1; i < n; i++){
        max_val = Math.max(max_val,arr[i]);
        max_val++;
        }
    ArrayList<ArrayList<Integer>> bucket = new ArrayList<ArrayList<Integer>>();
    for(int i = 0; i < k; i++){
        bucket.add(new ArrayList<Integer>());
    }
    for(int i=0; i < n; i++){
        int bucketI =(k * arr[i]/max_val;
        bucket.get(bucketI).add(arr[i]);
    }
    for(int i = 0; i < k; i++){
        Collections.sort(bucket.get(i));
    }
    int index = 0;
    for(int i=0; i < k; i++){
        for(int j=0; j < bucket.get(i).size().j++){
        arr[index++] = bucket.get(i).get(j);
        }
    }
}

Other important points:

• Radix sort uses counting sort as a sub routine to sort elements.
• The time complexity of bucket sort depends on the time complexity of the chosen subroutine sorting algorithm.
• Radix sort better than counting sorting when the range is greater than linear.
• Counting sort is a stable linear sorting algorithm.
• Radix sort, counting sort and bucket.
• Counting sort cannot be used to sort a linked list.
• Bucket sort on the other hand can be used to sort a linked list.

With this article at OpenGenus, the differences between Counting Sort vs Radix Sort vs Bucket Sort.