Counting Sort: A New Pespective on Sorting

For example, if the input array nums contains two 1s, one 3, and three 6s, then we just need to fill the array with two 1s, one 3, and three 6s in order. The sorted result is [1, 1, 3, 6, 6, 6].

Let’s look at a simple problem to understand this. See LeetCode Problem 75: “Sort Colors”:

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

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

There are many ways to solve this problem. The best way uses the two-pointer technique to sort the array in one pass. I will explain this in Array Two-Pointer Practice Problems. Here, we use counting sort to solve it. In short, you need to sort an array where the values are only 0, 1, or 2.

We can create a count array of size 3. count[0], count[1], and count[2] store how many 0s, 1s, and 2s are in the array. Then we fill the original array in order according to 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. But this problem is easy because it only has three types of numbers: 0, 1, and 2. Next, let’s see a more general counting sort algorithm.

General Counting Sort

Although counting sort is simple, there are still some coding tricks in the general version.

Let’s start with the problems. Counting sort needs to use the values in the array as indexes in the count array. So we can ask:

1. Does this mean we can only use counting sort when all numbers in nums are non-negative integers? What if there are negative numbers? What about custom types?

2. Since counting sort only cares about how many times each value appears, and does not care about the order of the same numbers, is counting sort unstable?

3. Because counting sort uses the value of the element as the index of the count array, what if the largest value in the array is very large? Will the count array use too much space?

Let’s think about these questions step by step and try to solve them.

Handling Negative Numbers and Custom Types

Accumulate the count Array to Avoid Using the Reverse Function

Space Complexity

Time Complexity

Non-comparison Sort