If you have a few years of experience in the Java ecosystem and you'd like to share that with the community, have a look at our **Contribution Guidelines**.

# Counting Sort in Java

Last modified: June 23, 2022

## 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 11^{th} 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 4^{th} 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Â*i*element in theÂ^{th}Â*inputÂ*should be theÂ*C[i]*element in the sorted array. Since Java arrays are zero-indexed, the^{th}Â*C[i]-1*entry isÂ theÂ*C[i]*element – for example,^{th}Â*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!