Counting Sort: A New Pespective on Sorting

For example, given an array nums, if I count 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 solve a simple problem to understand this. Consider 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]

This problem can be solved in multiple ways. The optimal solution uses the two-pointer technique to sort the array in a single pass. I will introduce this technique in Array Two-Pointer Technique Exercises. Here, we use the counting sort approach to solve this problem, which essentially requires you to sort the array containing 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, respectively. Then, we fill the original array according to the count array results.

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 scenario given in this problem is relatively simple, with only 0, 1, 2 as elements. Below, we provide a more general counting sort algorithm.

General Counting Sort

Although the principle of counting sort is simple, there are some coding techniques within the general counting sort code.

Let us start with the questions. Counting sort requires using the elements in the array as indices of the count array to count, which raises the following questions:

1. Does this mean that counting sort can only be used when all elements in the nums array are non-negative integers? How do we sort when 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 the relative position of identical elements. So, it seems that counting sort is an unstable sort, correct?

3. Since counting sort uses the element values as indices of the count array, if the maximum element value in the array is very large, will it cause the count array to be too large, leading to high space complexity?

Let us think through these questions step by step and try to provide solutions.