## 1. Overview

General-purpose sorting algorithms like Merge Sort make no assumption about the input, so they can’t beat the O(n log n)Â in the worst case. Counting Sort, on the contrary, has an assumption about the input which makes it a linear time sorting algorithm.

In this tutorial, we’re going to get acquainted with the mechanics of the Counting Sort and then implement it in Java.

## 2. Counting Sort

Counting sort, as opposed to most classic sorting algorithms, does not sort the given input by comparing the elements. Instead, it assumes that the input elements are nÂ integers in the range [0, k]. WhenÂ k = O(n),Â then the counting sort will run in O(n) time.

Please note, then, that we can’t use the counting sort as a general-purpose sorting algorithm. However, when the input is aligned with this assumption, it’s pretty fast!

### 2.1. Frequency Array

Let’s suppose we’re going to sort an input arrayÂ with values in the [0, 5] range:

First, we should count the occurrence of each number in the input array. If we represent the countings with array C, thenÂ C[i]Â represents the frequency of numberÂ iÂ in the input array:

For example, since 5 appears 3 times in the input array, the value for the index 5 is equal to 3.

Now given the arrayÂ C, we should determine how many elements are less than or equal to each input element.Â For example:

• One element is less than or equal to zero, or in other words, there is only one zero value, which is equal to C[0]
• Two elements are less than or equal to one, which is equal toÂ C[0] + C[1]
• Four values are less than or equal to two, which is equal toÂ C[0] + C[1] + C[2]

So if we keep computing the summation ofÂ nÂ consecutive elements inÂ C,Â we can know how many elements are less than or equal to numberÂ n-1 in the input array.Â Anyway, by applying this simple formula we can update theÂ CÂ as the following:

### 2.2. The Algorithm

Now we can use the auxiliary array CÂ to sort the input array. Here’s how the counting sort works:

• It iterates the input array in reverse
• For each elementÂ i,Â C[i] – 1Â represents the location of numberÂ i in the sorted array. This is because of the fact that there areÂ C[i]Â elements less than or equal toÂ i
• Then, it decrements theÂ C[i]Â at the end of each round

In order to sort the sample input array, we should first start with the number 5, since it’s the last element. According to C[5],Â there are 11 elements are less than or equal to the number 5.

So, 5 should be the 11th element in the sorted array, hence the index 10:

Since we moved 5 to the sorted array, we should decrement theÂ C[5].Â Next element in the reversed order is 2. Since there are 4 elements less than or equal to 2, this number should be the 4th element in the sorted array:

Similarly, we can find the right spot for the next element which is 0:

If we keep iterating in reverse and move each element appropriately, we would end up with something like:

## 3. Counting Sort – Java Implementation

### 3.1. Computing the Frequency Array

First off, given an input array of elements and theÂ k,Â we should compute the arrayÂ C:

``````int[] countElements(int[] input, int k) {
int[] c = new int[k + 1];
Arrays.fill(c, 0);

for (int i : input) {
c[i] += 1;
}

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

return c;
}``````

Let’s breakdown the method signature:

• inputÂ represents an array of numbers we’re going to sort
• The input array is an array of integers in the range of [0, k] – so kÂ represents the maximum number in theÂ input
• The return type is an array of integers representing theÂ CÂ array

And here’s how the countElementsÂ method works:

• First, we initialized theÂ CÂ array. As the [0, k] range containsÂ k+1Â numbers, we’re creating an array capable of containingÂ k+1Â numbers
• Then for each number in theÂ input,Â we’re computing the frequency of that number
• And finally, we’re adding consecutive elements together to know how many elements are less than or equal to a particular number

Also, we can verify that theÂ countElementsÂ method works as expected:

``````@Test
void countElements_GivenAnArray_ShouldCalculateTheFrequencyArrayAsExpected() {
int k = 5;
int[] input = { 4, 3, 2, 5, 4, 3, 5, 1, 0, 2, 5 };

int[] c = CountingSort.countElements(input, k);
int[] expected = { 1, 2, 4, 6, 8, 11 };
assertArrayEquals(expected, c);
}``````

### 3.2. Sorting the Input Array

Now that we can calculate the frequency array, we should be able to sort any given set of numbers:

``````int[] sort(int[] input, int k) {
int[] c = countElements(input, k);

int[] sorted = new int[input.length];
for (int i = input.length - 1; i >= 0; i--) {
int current = input[i];
sorted[c[current] - 1] = current;
c[current] -= 1;
}

return sorted;
}``````

Here’s how theÂ sortÂ method works:

• First, it computes theÂ CÂ array
• Then, it iterates the inputÂ array in reverse and for each element in theÂ input,Â finds its correct spot in the sorted array. TheÂ ithÂ element in theÂ inputÂ should be theÂ C[i]thÂ element in the sorted array. Since Java arrays are zero-indexed, the C[i]-1 entry isÂ theÂ C[i]thÂ element – for example, sorted[5]Â is the sixth element in the sorted array
• Each time we find a match, it decrements the corresponding C[i]Â value

Similarly, we can verify that theÂ sortÂ method works as expected:

``````@Test
void sort_GivenAnArray_ShouldSortTheInputAsExpected() {
int k = 5;
int[] input = { 4, 3, 2, 5, 4, 3, 5, 1, 0, 2, 5 };

int[] sorted = CountingSort.sort(input, k);

// Our sorting algorithm and Java's should return the same result
Arrays.sort(input);
assertArrayEquals(input, sorted);
}``````

## 4. Revisiting the Counting Sort Algorithm

### 4.1. Complexity Analysis

Most classic sorting algorithms, like merge sort, sort any given input by just comparing the input elements to each other.Â These type of sorting algorithms are known asÂ comparison sorts. In the worst case, comparison sorts should take at least O(n log n)Â to sort nÂ elements.

Counting Sort, on the other hand, does not sort the input by comparing the input elements, so it’s clearly not a comparison sort algorithm.

Let’s see how much time it consumes to sort the input:

• It computes theÂ CÂ array inÂ O(n+k)Â time: It once iterates an input array with size nÂ inÂ O(n)Â and then iterates theÂ CÂ inÂ O(k) – soÂ that would be O(n+k)Â in total
• After computing theÂ C,Â it sorts the input by iterating the input array and performing a few primitive operations in each iteration. So, the actual sort operation takes O(n)

In total, counting sort takesÂ O(n+k)Â time to run:

``O(n + k) + O(n) = O(2n + k) = O(n + k)``

If we assumeÂ k=O(n),Â then counting sort algorithm sorts the input in linear time.Â As opposed to general-purpose sorting algorithms, counting sorts makes an assumption about the input and takes less than the O(n log n)Â lower bound to execute.

### Â 4.2. Stability

A few moments ago, we laid a few peculiar rules about the mechanics of counting sort but never cleared the reason behind them. To be more specific:

• Why should we iterate the input array in reverse?
• Why we decrement theÂ C[i]Â each time we’re using it?

Let’s iterate from the beginning to better understand the first rule. Suppose we’re going to sort a simple array of integers like the following:

In the first iteration, we should find the sorted location for the first 1:

So the first occurrence of number 1 gets the last index in the sorted array. Skipping the number 0, let’s see what happens to the second occurrence of number 1:

The appearance order of elements with the same value is different in the input and sorted array, so the algorithm is not stable when we’re iterating from the beginning.

What happens if we don’t decrement theÂ C[i]Â value after each use? Let’s see:

Both occurrences of number 1 are getting the last place in the sorted array. So if we don’t decrement theÂ C[i]Â value after each use, we could potentially lose a few numbers while sorting them!

## 5. Conclusion

In this tutorial, first, we learned how the Counting Sort works internally. Then we implemented this sorting algorithm in Java and wrote a few tests to verify its behavior. And finally, we proved that the algorithm is a stable sorting algorithm with linear time complexity.

As usual, the sample codes are available on our GitHub project, so make sure to check it out!

Get started with Spring Boot and with core Spring, through the Learn Spring course:

>> CHECK OUT THE COURSE

1 Comment
Inline Feedbacks