Counting Sort Program in Java

In this tutorial, we’ll walk through how to implement a Counting Sort Program in Java. Counting Sort is a linear‑time sorting algorithm with a time complexity of O(N + K), making it faster than comparison‑based algorithms such as Merge sort and Quick sort when the input range is limited. It belongs to the family of non‑comparison sorting techniques, alongside Radix Sort and Bucket Sort.

Advantages and Limitations

Though counting sort is one of the fastest sorting algorithm but it has certain drawbacks too. One of them is that the algorithm requires prior knowledge of the input range. Counting sort also needs auxiliary space as it needs to store the frequency of elements. This makes it less memory‑efficient for datasets with very large ranges.

How does counting sort work

Counting sort works by counting the frequency of each element to create a frequency array or count array. Then these counts are used to compute the index of an element in the sorted array. The process can be broken down into following steps:

Initialize Count Array
Create a count array to store the frequency count of each element. If the range of elements is 0 to k then count array should be of length k+1. For example, if max element in the array is 15 then count array should be of length 16.
Populate Frequency Counts
Iterate through the elements in input array and for each element increment its count in the corresponding index in the count array.
For example, if input array is- [0, 4, 2, 6, 5, 4, 8, 9, 8, 6]

Then the count array would be like below-
Compute Prefix Sums
Transform the count array so that each index stores the sum of element at current index + element at previous index (prefix sum array).
Build Sorted Output
Using this modified count array you need to construct the sorted array. For that you take an element from the input array and go to that index in the modified count array to get a value. That value is the place, of the element picked from the input array, in the sorted array.
In the count array decrement the value by 1 too.
For example if input array and modified count array are as follows-

First element in the input array is 0, so consult the 0th index in the count array which is 1. That means 0 goes at the place 1 (i.e. index 0) in the sorted array. Decrement the value in the count array too. In this step value at index 0 in the count array will be decremented by 1 so that it becomes 0.

Second element in the input array is 4, so consult the 4th index in the count array which is 4. That means 4 goes at the place 4 (i.e. index 3) in the sorted array. With in input array an element may be repeated and those should be grouped together. For that we need to decrement the value in the count array. In this step value at index 4 in the count array will be decremented by 1 so that it becomes 3.

When the next 4 is encountered in the input array value at the 4th index in the count array will be 3. That means next 4 goes at the place 3 (i.e. index 2) in the sorted array.

Counting Sort Java program

public class CountingSort {

  public static void main(String[] args) {
    int[] arr = {0, 4, 2, 6, 5, 4, 8, 9, 8, 6};
    // max element + 1
    int range = 10;
    System.out.println("Original Array- " + Arrays.toString(arr));
    arr = countingSort(arr, range);
    System.out.println("Sorted array after counting sort- " + Arrays.toString(arr));
  }
    
  private static int[] countingSort(int[] arr, int range){
    int[] output = new int[arr.length];
    int[] count = new int[range];
    //count number of times each element appear
    for(int i = 0; i < arr.length; i++){
      count[arr[i]]++;
    }
    System.out.println("Count array- " + Arrays.toString(count));
    // each element stores (sum of element at current index 
    //+ element at previous index)
    for(int i = 1; i < range; i++){
      count[i] = count[i] + count[i-1];
    }
    System.out.println("Modified count- " + Arrays.toString(count));
    for(int i = 0; i < arr.length; i++){
      output[count[arr[i]] - 1] = arr[i];
      count[arr[i]]--;
    }
    return output;
  }
}

Output

Original Array- [0, 4, 2, 6, 5, 4, 8, 9, 8, 6]
Count array- [1, 0, 1, 0, 2, 1, 2, 0, 2, 1]
Modified count- [1, 1, 2, 2, 4, 5, 7, 7, 9, 10]
Sorted array after counting sort- [0, 2, 4, 4, 5, 6, 6, 8, 8, 9]

Performance of Counting Sort

If the number of elements to be sorted is n and the range of elements is 0-k then the time complexity of Counting sort can be calculated as-

Loop to create count array takes O(n) time. Second loop where count array is modified takes O(k) time and creating sorted output array again takes O(n) time. Thus the time complexity with all these combined comes as O(2n+k). Since constants are not taken into consideration so the time complexity of Counting sort is O(n+k).

Auxiliary space requirement is also (n+k). Count array takes k space and the output array n. Thus the space complexity of Counting sort is O(n+k).

That's all for this topic Counting Sort Program in Java. If you have any doubt or any suggestions to make please drop a comment. Thanks!

>>>Return to Java Programs Page

Related Topics

You may also like-

Tech Tutorials

Sunday, April 5, 2026