Counting Sort: A New Pespective on Sorting

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 1s, 1 3, and 3 6s to get the sorted result [1, 1, 3, 6, 6, 6].

Let's understand this with a simple problem, 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 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:

1. 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?

2. 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?

3. 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.