# Counting Sort: A New Pespective on Sorting

Prerequisite Knowledge

Before reading this article, you should first learn:

Summary in One Sentence

The principle of counting sort is relatively simple: count the occurrences of each element to deduce the index position of each element in the sorted array, thus completing the sorting.

The time and space complexity of counting sort are both $O(n + max - min)$, where $n$ is the length of the array to be sorted, and $max - min$ is the range of the elements in the array to be sorted.

This is the visualization panel for selection sort. You can click on the code `sorted[count[index] - 1] = nums[i]`

to see the process of forming the sorted array:

For example, given an input array `nums`

, if I find that there are 2 elements of `1`

, 1 element of `3`

, and 3 elements of `6`

, I can fill the array with 2 `1`

s, 1 `3`

, and 3 `6`

s to get the sorted result `[1, 1, 3, 6, 6, 6]`

.

Let's understand this with a simple problem, LeetCode Problem 75 "Sort Colors":

**75. Sort Colors** | LeetCode |

Given an array `nums`

with `n`

objects colored red, white, or blue, sort them **in-place **so that objects of the same color are adjacent, with the colors in the order red, white, and blue.

We will use the integers `0`

, `1`

, and `2`

to represent the color red, white, and blue, respectively.

You must solve this problem without using the library's sort function.

**Example 1:**

Input:nums = [2,0,2,1,1,0]Output:[0,0,1,1,2,2]

**Example 2:**

Input:nums = [2,0,1]Output:[0,1,2]

**Constraints:**

`n == nums.length`

`1 <= n <= 300`

`nums[i]`

is either`0`

,`1`

, or`2`

.

**Follow up:** Could you come up with a one-pass algorithm using only constant extra space?

There are multiple approaches to solve this problem. The optimal solution uses the two-pointer technique to sort the array in a single pass. I will introduce this technique in the Array Two-Pointer Technique Exercises. Here, we will use the counting sort approach to solve this problem. Essentially, it requires sorting an array that contains only the elements 0, 1, and 2.

We can create a `count`

array of size 3, where `count[0], count[1], count[2]`

represent the number of occurrences of 0, 1, and 2 in the array, respectively. Then, we fill the original array according to the results in the `count`

array.

```
class Solution {
public void sortColors(int[] nums) {
// count the number of 0, 1, 2
int[] count = new int[3];
for (int element : nums) {
count[element]++;
}
// fill the original array according to the count array
int index = 0;
for (int element = 0; element < 3; element++) {
for (int i = 0; i < count[element]; i++) {
nums[index] = element;
index++;
}
}
}
}
```

```
class Solution {
public:
void sortColors(vector<int>& nums) {
// count the number of 0, 1, 2
vector<int> count(3, 0);
for (int element : nums) {
count[element]++;
}
// fill the original array according to the count array
int index = 0;
for (int element = 0; element < 3; element++) {
for (int i = 0; i < count[element]; i++) {
nums[index] = element;
index++;
}
}
}
};
```

```
class Solution:
def sortColors(self, nums: List[int]) -> None:
# count the number of 0, 1, 2
count = [0] * 3
for element in nums:
count[element] += 1
# fill the original array according to the count array
index = 0
for element in range(3):
for _ in range(count[element]):
nums[index] = element
index += 1
```

```
func sortColors(nums []int) {
// count the number of 0, 1, 2
count := make([]int, 3)
for _, element := range nums {
count[element]++
}
// fill the original array according to the count array
index := 0
for element := 0; element < 3; element++ {
for i := 0; i < count[element]; i++ {
nums[index] = element
index++
}
}
}
```

```
var sortColors = function(nums) {
// count the number of 0, 1, 2
const count = [0, 0, 0];
for (const element of nums) {
count[element]++;
}
// fill the original array according to the count array
let index = 0;
for (let element = 0; element < 3; element++) {
for (let i = 0; i < count[element]; i++) {
nums[index] = element;
index++;
}
}
};
```

This is a simple counting sort algorithm. However, the problem scenario is straightforward, involving only three types of elements: `0, 1, 2`

. Below, we present a more general counting sort algorithm.

## General Counting Sort

Although the principle of counting sort is simple, there are several coding techniques involved in a general counting sort code.

Let's start by posing some questions. Counting sort requires using the elements of an array as indices for the `count`

array to perform counting. This raises the following concerns:

Does counting sort only work when the elements in the

`nums`

array are non-negative integers? How can we sort if there are negative numbers? How do we sort custom types?Based on the principle of counting sort, we only care about how many times a particular element appears, not about the relative position of identical elements. Does this mean that counting sort is inherently unstable?

Since counting sort uses the value of elements as indices in the

`count`

array, what happens if the maximum element value in the array is very large? Would this result in an excessively large`count`

array, leading to high space complexity?

Let's consider these questions one by one and attempt to provide solutions.