## Introduction

Counting sort is a sorting algorithm used to sort elements of an array in **linear time**. We usually use Counting Sort to sort integer arrays.

Counting Sort a

stable,non-comparative algorithm.

**Non-comparative** sorting algorithms perform sorting without any comparison between elements to be sorted.

**Stable** sorting algorithms preserve the relative order of elements with the same value in the sorted array. That means that the relative order of two same-value elements in the original array will be the same as their relative order in the sorted array.

Counting sort is **not an in-place algorithm**, it uses an auxiliary array to sort elements of an input array.

- How does Counting Sort Work?
- Python Implementation of Counting Sort
- The Complexity of the Counting Sort Algorithm

## How Does Counting Sort Work?

Let's first take an intuitive look at how the algorithm works.

Assume that we have the array `I = [2, 2, 0, 6, 1, 9, 9, 7]`

and we want to sort it. We'll call the array `I`

the * input array*.

Counting Sort works by counting the number of elements that fit a distinct key value, and then calculates the positions of each key.

First of all, we need to find the element with the highest value, we'll call it the maximum element - `maxElement = 9`

.

Then, we'll create an auxiliary array with `maxElement+1`

elements, called the * count array (C)*. We'll use it to store the number of occurrences of each individual element in the

*input array*

`I`

. Therefore, all counts should be initialized to 0:```
C = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0] # Count array
# indices: 0 1 2 3 4 5 6 7 8 9
```

**Now, we need to go through the following steps:**

**1.** Go over each element of the *input array* and increase its corresponding count by `1`

For example, if we come across an element with the value of `2`

in the *input array* (`I`

), we add 1 to the element with the index `2`

in the *count array*:

```
I = [2, 2, 0, 6, 1, 9, 9, 7] # The first element is 2
^
C = [0, 0, 1, 0, 0, 0, 0, 0, 0, 0] # We increase count of 2nd element by 1
#indices: 0 1 2 3 4 5 6 7 8 9
```

After this step, the *count array* will store the number of occurrences of each element in the *input array*:

```
C = [1, 1, 2, 0, 0, 0, 1, 1, 0, 2]
#indices: 0 1 2 3 4 5 6 7 8 9
# Element 0 has 1 occurrence
# Element 1 has 1 occurrence
# Element 2 has 2 occurrences
# Element 3 has no occurrences...
```

**2.** For each element in the *count array*, sum up its value with the value of all its previous elements, and store that value as the value of the current element:

```
C = [1, 2, 4, 4, 4, 4, 5, 6, 6, 8]
#indices: 0 1 2 3 4 5 6 7 8 9
# Element 0 = 1
# Element 1 = 1 + 1
# Element 2 = 1 + 1 + 2
# Element 3 = 1 + 1 + 2 + 0
#...
```

This way, we are storing the cumulative sum of the elements of the *count array*, on each step.

**3.** Calculate element position based on the *count array* values:

To store this sorted sequence, we'll need to create a new array. Let's call it the *output array* (`O`

), and initialize it with `k`

zeros, where `k`

is the number of elements in the *input array*:

```
O = [0, 0, 0, 0, 0, 0, 0, 0] // Initialized output array
#indices: 0 1 2 3 4 5 6 7
```

For each element`I[i]`

(starting from the end) in theinput array:Free eBook: Git EssentialsCheck out our hands-on, practical guide to learning Git, with best-practices, industry-accepted standards, and included cheat sheet. Stop Googling Git commands and actually

learnit!

- Find the index in the
count arraythat is equal to the value of the current element`I[i]`

- That's the element
`C[j]`

where`j=I[i]`

- Subtract
`1`

from the value of the`C[i]`

- Now we have
`newValue = C[i]-1`

- Store the
`I[i]`

to the`O[newValue]`

- Update the
`C[i]`

with the`newValue`

In the end, the *output array* contains the sorted elements of the input array!

## Counting Sort - Python Implementation

Now, with all that out of the way - let's go ahead and implement Counting Sort in Python:

```
def countingSort(inputArray):
# Find the maximum element in the inputArray
maxElement= max(inputArray)
countArrayLength = maxElement+1
# Initialize the countArray with (max+1) zeros
countArray = [0] * countArrayLength
# Step 1 -> Traverse the inputArray and increase
# the corresponding count for every element by 1
for el in inputArray:
countArray[el] += 1
# Step 2 -> For each element in the countArray,
# sum up its value with the value of the previous
# element, and then store that value
# as the value of the current element
for i in range(1, countArrayLength):
countArray[i] += countArray[i-1]
# Step 3 -> Calculate element position
# based on the countArray values
outputArray = [0] * len(inputArray)
i = len(inputArray) - 1
while i >= 0:
currentEl = inputArray[i]
countArray[currentEl] -= 1
newPosition = countArray[currentEl]
outputArray[newPosition] = currentEl
i -= 1
return outputArray
inputArray = [2,2,0,6,1,9,9,7]
print("Input array = ", inputArray)
sortedArray = countingSort(inputArray)
print("Counting sort result = ", sortedArray)
```

Running the code above will produce the following output:

```
Input array = [2, 2, 0, 6, 1, 9, 9, 7]
Counting sort result = [0, 1, 2, 2, 6, 7, 9, 9]
```

## The Complexity of the Counting Sort Algorithm

The Counting sort algorithm uses only simple *for* and *while* loops without any complex recursions and subroutine calls, therefore, its complexity analysis is a pretty straightforward process.

Before we dive into the complexity analysis, let's label the length of the input array as `n`

and the value of the maximum element in the input array as `k`

.

### Time Complexity

The first step of the algorithm iterates over the input array n times in order to initialize the count array, so it has the complexity of **O(n)**.

The second step iterates over the count k times in order to calculate the cumulative sum of each element, so it has the complexity of **O(k)**.

The third step performs the sorting based on the counting array, so it has to iterate in a while loop `n`

times, therefore it has the complexity of **O(n)**.

Collectively, **the time complexity of the Counting Sort algorithm is O(n+k).**

### Space Complexity

Counting sort uses *input* and *output array,* both of length `n`

and one *count array* of length `(k+1)`

.

Therefore, **the total space that this algorithm uses is O(n+k).**

## Conclusion

All in all, Counting Sort is a great and efficient, yet simple sorting algorithm. In ideal circumstances, it is really easy to understand and learn but still manages to maintain linear complexity.

The real problem occurs when the value of the largest element `k`

exceeds the number of elements in the input array `n`

. As the `k`

approaches `n²`

, the time complexity of counting sort gets closer to `O(n²)`

, which is a horrible time complexity for a sorting algorithm. Therefore, it's not recommended to use counting sort if the input array has a large range of values.

Ideally, we will use Counting Sort to sort some integer arrays with a small range of values or as a subroutine for some other sorting algorithm, such as Radix Sort. That way, we will ensure maximizing the full potential of the counting sort, while still avoiding all of the suboptimal use cases.