How to Implement the Counting Sort Algorithm

Introduction

When you think of sorting algorithms, you probably think of the classic ones—Bubble Sort, Merge Sort, or Quick Sort. But did you know there’s a linear time sorting algorithm that doesn’t rely on comparisons? Meet Counting Sort.

In this blog post, we’ll break down how Counting Sort works, where it shines, and how to implement it in Java.

What is Counting Sort?

Counting Sort is a sorting algorithm on integers. It works by counting the number of occurrences of each unique value in the input array. It’s particularly efficient when:

• The range of input values (max – min) is not significantly larger than the number of elements.
• The input consists of non-negative integers (or can be normalized).

Time Complexity:

• Best/Average/Worst Case: O(n + k)
  where n is the number of elements and k is the range of input.

Space Complexity:

• O(k) for the count array.

How It Works (Step by Step)

1. Find the maximum value in the array and so the size of the count array.
2. Create and populate a count array where each index corresponds to a value in the input.
3. Modify the count array such that each element stores the sum of previous counts (to determine positions).
4. Build the output array using the count array.
5. Copy the output array back to the original input array (if needed).

Counting Sort Java Implementation

	@Test
	public void CountingSortTest() throws Exception {
        int[] arrToBeSorted = {13, 15, 21, 57, 67, 71};   
        cSort(arrToBeSorted);
        for (int elem : arrToBeSorted) {
            System.out.println(elem + " ");
        }
	}
	
    public static void cSort(int[] arrToBeSorted) {
        if (arrToBeSorted.length == 0) return;
        int max = Arrays.stream(arrToBeSorted).max().getAsInt();
        int[] countArray = new int[max + 1];

        for (int num : arrToBeSorted) {
        	countArray[num]++;
        }

        for (int i = 1; i < countArray.length; i++) {
        	countArray[i] += countArray[i - 1];
        }

        int[] output = new int[arrToBeSorted.length];
        for (int i = arrToBeSorted.length - 1; i >= 0; i--) {
            output[--countArray[arrToBeSorted[i]]] = arrToBeSorted[i];
        }
        System.arraycopy(output, 0, arrToBeSorted, 0, arrToBeSorted.length);
    }

Limitations

• Not appropriate for floating-point numbers or negative numbers.
• The used space might be ample if the range of input values is large.
• It’s not a comparison sort, so it cannot replace general-purpose sorting.

Conclusion

Counting Sort is not the most known sorting algorithm. When its used appropriately, though, especially for small integers with limited range, it offers great performance. It’s an excellent tool to use when the need arises.

You can find the example code on Github.