Counting Sort Algorithm

Implementation in Java, an analysis of stability, parallelizability, and the Time and Space Complexities

We have seen sorting algorithms in the earlier article. Also, in the previous article, we have discussed the Counting Sort Algorithm.

In this article, we are going to see the implementation of the algorithm, analysis of stability, parallelizability, and the Time and Space Complexities of the Counting Sort Algorithm.

How to formulate the algorithm?

countingSort(array, size)
  max <- find largest element in array
  initialize count array with all zeros
  for j <- 0 to size
    find the total count of each unique element and 
    store the count at jth index in count array
  for i <- 1 to max
    find the cumulative sum and store it in count array itself
  for j <- size down to 1
    restore the elements to array
    decrease count of each element restored by 1

Implement the Counting Sort Algorithm in Java

import java.util.Arrays;
public class CountingSort {
   public static int findMax(int [] elements) {
      // Find the largest element of the array
      int max = elements[0];
      for (int i = 1; i < elements.length; i++) {
          if (elements[i] > max)
          max = elements[i];
      }
   return max;
   }
  
   public static void sort(int[] elements) {
      int maxValue = findMax(elements);
      int[] counts = new int[maxValue + 1];
      // Phase 1: Count
      for (int i = 0; i < elements.length; i++) {
          counts[elements[i]]++;
      }
      // Phase 2: Aggregate
      for (int i = 1; i <= maxValue; i++) {
          counts[i] += counts[i - 1];
      }
      // Phase 3: Write to target array
      int[] target = new int[elements.length];
      for (int i = elements.length - 1; i >= 0; i--) {
          int element = elements[i];
          target[--counts[element]] = element;
      }
      // Copy target back to input array
      System.arraycopy(target, 0, elements, 0, elements.length);
  
      //Print the array
      printArray(elements);
   }
  
   public static void printArray(int [] elements) {
      // Print the sorted array
      System.out.println(Arrays.toString(elements));
   }
   public static void main(String [] args) {
      // Array to be sorted
      int elements [] = {3,7,4,6,6,3,0,3,8,6,6,9,6,2,8};
      sort(elements);
   }
}

What will be the output?

[0, 2, 3, 3, 3, 4, 6, 6, 6, 6, 6, 7, 8, 8, 9]

Another example

Time and Space Complexities

There are few numbers of for loops in this execution. Consider the for loops in the three phases of the execution.

// Count
for (int i = 0; i < elements.length; i++) {
      counts[elements[i]]++;
}
// Aggregate
for (int i = 1; i <= maxValue; i++) {
      counts[i] += counts[i - 1];
}
// Write to target array
int[] target = new int[elements.length];
for (int i = elements.length - 1; i >= 0; i--) {
      int element = elements[i];
      target[--counts[element]] = element;
}

Therefore, the overall time complexity = O(size)+O(max)+O(size) = O(max+size)

1. Worst Case Complexity: O(max+size)
2. Best Case Complexity: O(max+size)
3. Average Case Complexity: O(max+size)

The complexity is the same in all of the preceding cases because the algorithm runs through max+size times regardless of how the elements are arranged in the array.

Counting Sort has a space complexity of O(max+size). The greater the range of elements, the greater the space complexity.

Stability of Counting Sort

The Counting Sort algorithm iterates from right to left over the input array while Writing Back Sorted Objects, copying objects with the same key from right to left into the output array. As a result, Counting Sort is a stable sorting algorithm.

Parallelizability of Counting Sort

Counting Sort can be parallelized by partitioning the input array into as many partitions as there are readily accessible processors.

Each processor counts the elements of “its” partition in a separate auxiliary array during Counting the Elements. During Aggregating the Histogram, all auxiliary arrays are incorporated together to form one. During Writing Back Sorted Objects, each processor copies “its” partition’s elements to the target array. The fields in the auxiliary array must be decremented and read atomically.

Because of parallelization, it is no longer possible to guarantee that elements with the same key are copied to the target array in the same order. As a result, the Parallel Counting Sort is not stable.

Point to think : What will happen if the array to be sorted is this? Will you still prefer to use Counting Sort? Why?
{10, 50, 100000, 500, 30, 900, 5}

Hope the article can help. Share your thoughts too.