Skip to content
Welcome to contribute to Chinese-to-English translation! For more details, please refer to CONTRIBUTING.md.

# 11.9 Counting Sort

Counting sort sorts by counting the occurrences of elements and is typically applied to integer arrays.

## 11.9.1 Simple Implementation

Let's start with a simple example. Given an array `nums` of length \(n\), where the elements are all "non-negative integers", the overall flow of counting sort is shown in Figure 11-16.

1. Traverse the array to find the largest number, denoted as \(m\), and then create an auxiliary array `counter` of length \(m + 1\).
2. Use `counter` to count how many times each number appears in `nums`, where `counter[num]` stores the number of occurrences of `num`. This is simple: traverse `nums` (denote the current number by `num`) and increment `counter[num]` by \(1\) each time.
3. Because the indices of `counter` are naturally ordered, the numbers are effectively already sorted. Next, traverse `counter` and write the numbers back into `nums` in ascending order according to their occurrence counts.

Figure 11-16 Counting sort flow

The code is as follows:

Python C++Java C#Go Swift JS TS Dart Rust C Kotlin Ruby
counting_sort.py

    def counting_sort_naive(nums: list[int]):
        """Counting sort"""
        # Simple implementation, cannot be used for sorting objects
        # 1. Count the maximum element m in the array
        m = 0
        for num in nums:
            m = max(m, num)
        # 2. Count the occurrence of each number
        # counter[num] represents the occurrence of num
        counter = [0] * (m + 1)
        for num in nums:
            counter[num] += 1
        # 3. Traverse counter, filling each element back into the original array nums
        i = 0
        for num in range(m + 1):
            for _ in range(counter[num]):
                nums[i] = num
                i += 1

counting_sort.cpp

    /* Counting sort */
    // Simple implementation, cannot be used for sorting objects
    void countingSortNaive(vector<int> &nums) {
        // 1. Count the maximum element m in the array
        int m = 0;
        for (int num : nums) {
            m = max(m, num);
        }
        // 2. Count the occurrence of each number
        // counter[num] represents the occurrence of num
        vector<int> counter(m + 1, 0);
        for (int num : nums) {
            counter[num]++;
        }
        // 3. Traverse counter, filling each element back into the original array nums
        int i = 0;
        for (int num = 0; num < m + 1; num++) {
            for (int j = 0; j < counter[num]; j++, i++) {
                nums[i] = num;
            }
        }
    }

counting_sort.java

    /* Counting sort */
    // Simple implementation, cannot be used for sorting objects
    void countingSortNaive(int[] nums) {
        // 1. Count the maximum element m in the array
        int m = 0;
        for (int num : nums) {
            m = Math.max(m, num);
        }
        // 2. Count the occurrence of each number
        // counter[num] represents the occurrence of num
        int[] counter = new int[m + 1];
        for (int num : nums) {
            counter[num]++;
        }
        // 3. Traverse counter, filling each element back into the original array nums
        int i = 0;
        for (int num = 0; num < m + 1; num++) {
            for (int j = 0; j < counter[num]; j++, i++) {
                nums[i] = num;
            }
        }
    }

counting_sort.cs

    /* Counting sort */
    // Simple implementation, cannot be used for sorting objects
    void CountingSortNaive(int[] nums) {
        // 1. Count the maximum element m in the array
        int m = 0;
        foreach (int num in nums) {
            m = Math.Max(m, num);
        }
        // 2. Count the occurrence of each number
        // counter[num] represents the occurrence of num
        int[] counter = new int[m + 1];
        foreach (int num in nums) {
            counter[num]++;
        }
        // 3. Traverse counter, filling each element back into the original array nums
        int i = 0;
        for (int num = 0; num < m + 1; num++) {
            for (int j = 0; j < counter[num]; j++, i++) {
                nums[i] = num;
            }
        }
    }

counting_sort.go

    /* Counting sort */
    // Simple implementation, cannot be used for sorting objects
    func countingSortNaive(nums []int) {
        // 1. Count the maximum element m in the array
        m := 0
        for _, num := range nums {
            if num > m {
                m = num
            }
        }
        // 2. Count the occurrence of each number
        // counter[num] represents the occurrence of num
        counter := make([]int, m+1)
        for _, num := range nums {
            counter[num]++
        }
        // 3. Traverse counter, filling each element back into the original array nums
        for i, num := 0, 0; num < m+1; num++ {
            for j := 0; j < counter[num]; j++ {
                nums[i] = num
                i++
            }
        }
    }

counting_sort.swift

    /* Counting sort */
    // Simple implementation, cannot be used for sorting objects
    func countingSortNaive(nums: inout [Int]) {
        // 1. Count the maximum element m in the array
        let m = nums.max()!
        // 2. Count the occurrence of each number
        // counter[num] represents the occurrence of num
        var counter = Array(repeating: 0, count: m + 1)
        for num in nums {
            counter[num] += 1
        }
        // 3. Traverse counter, filling each element back into the original array nums
        var i = 0
        for num in 0 ..< m + 1 {
            for _ in 0 ..< counter[num] {
                nums[i] = num
                i += 1
            }
        }
    }

counting_sort.js

    /* Counting sort */
    // Simple implementation, cannot be used for sorting objects
    function countingSortNaive(nums) {
        // 1. Count the maximum element m in the array
        let m = Math.max(...nums);
        // 2. Count the occurrence of each number
        // counter[num] represents the occurrence of num
        const counter = new Array(m + 1).fill(0);
        for (const num of nums) {
            counter[num]++;
        }
        // 3. Traverse counter, filling each element back into the original array nums
        let i = 0;
        for (let num = 0; num < m + 1; num++) {
            for (let j = 0; j < counter[num]; j++, i++) {
                nums[i] = num;
            }
        }
    }

counting_sort.ts

    /* Counting sort */
    // Simple implementation, cannot be used for sorting objects
    function countingSortNaive(nums: number[]): void {
        // 1. Count the maximum element m in the array
        let m: number = Math.max(...nums);
        // 2. Count the occurrence of each number
        // counter[num] represents the occurrence of num
        const counter: number[] = new Array<number>(m + 1).fill(0);
        for (const num of nums) {
            counter[num]++;
        }
        // 3. Traverse counter, filling each element back into the original array nums
        let i = 0;
        for (let num = 0; num < m + 1; num++) {
            for (let j = 0; j < counter[num]; j++, i++) {
                nums[i] = num;
            }
        }
    }

counting_sort.dart

    /* Counting sort */
    // Simple implementation, cannot be used for sorting objects
    void countingSortNaive(List<int> nums) {
      // 1. Count the maximum element m in the array
      int m = 0;
      for (int _num in nums) {
        m = max(m, _num);
      }
      // 2. Count the occurrence of each number
      // counter[_num] represents occurrence count of _num
      List<int> counter = List.filled(m + 1, 0);
      for (int _num in nums) {
        counter[_num]++;
      }
      // 3. Traverse counter, filling each element back into the original array nums
      int i = 0;
      for (int _num = 0; _num < m + 1; _num++) {
        for (int j = 0; j < counter[_num]; j++, i++) {
          nums[i] = _num;
        }
      }
    }

counting_sort.rs

    /* Counting sort */
    // Simple implementation, cannot be used for sorting objects
    fn counting_sort_naive(nums: &mut [i32]) {
        // 1. Count the maximum element m in the array
        let m = *nums.iter().max().unwrap();
        // 2. Count the occurrence of each number
        // counter[num] represents the occurrence of num
        let mut counter = vec![0; m as usize + 1];
        for &num in nums.iter() {
            counter[num as usize] += 1;
        }
        // 3. Traverse counter, filling each element back into the original array nums
        let mut i = 0;
        for num in 0..m + 1 {
            for _ in 0..counter[num as usize] {
                nums[i] = num;
                i += 1;
            }
        }
    }

counting_sort.c

    /* Counting sort */
    // Simple implementation, cannot be used for sorting objects
    void countingSortNaive(int nums[], int size) {
        // 1. Count the maximum element m in the array
        int m = 0;
        for (int i = 0; i < size; i++) {
            if (nums[i] > m) {
                m = nums[i];
            }
        }
        // 2. Count the occurrence of each number
        // counter[num] represents the occurrence of num
        int *counter = calloc(m + 1, sizeof(int));
        for (int i = 0; i < size; i++) {
            counter[nums[i]]++;
        }
        // 3. Traverse counter, filling each element back into the original array nums
        int i = 0;
        for (int num = 0; num < m + 1; num++) {
            for (int j = 0; j < counter[num]; j++, i++) {
                nums[i] = num;
            }
        }
        // 4. Free memory
        free(counter);
    }

counting_sort.kt

    /* Counting sort */
    // Simple implementation, cannot be used for sorting objects
    fun countingSortNaive(nums: IntArray) {
        // 1. Count the maximum element m in the array
        var m = 0
        for (num in nums) {
            m = max(m, num)
        }
        // 2. Count the occurrence of each number
        // counter[num] represents the occurrence of num
        val counter = IntArray(m + 1)
        for (num in nums) {
            counter[num]++
        }
        // 3. Traverse counter, filling each element back into the original array nums
        var i = 0
        for (num in 0..<m + 1) {
            var j = 0
            while (j < counter[num]) {
                nums[i] = num
                j++
                i++
            }
        }
    }

counting_sort.rb

    ### Counting sort ###
    def counting_sort_naive(nums)
      # Simple implementation, cannot be used for sorting objects
      # 1. Count the maximum element m in the array
      m = 0
      nums.each { |num| m = [m, num].max }
      # 2. Count the occurrence of each number
      # counter[num] represents the occurrence of num
      counter = Array.new(m + 1, 0)
      nums.each { |num| counter[num] += 1 }
      # 3. Traverse counter, filling each element back into the original array nums
      i = 0
      for num in 0...(m + 1)
        (0...counter[num]).each do
          nums[i] = num
          i += 1
        end
      end
    end

Connection between counting sort and bucket sort

From the perspective of bucket sort, each index of the counting array `counter` can be viewed as a bucket, and the counting process can be seen as distributing elements into their corresponding buckets. Essentially, counting sort is a special case of bucket sort for integer data.

## 11.9.2 Complete Implementation

Observant readers may have noticed that if the input consists of objects, step `3.` above no longer works. Suppose the input consists of product objects and we want to sort them by price (a member variable of the class); the above algorithm can only produce the sorted order of the prices themselves.

So how can we obtain the sorted order of the original data? We first compute the prefix sums of `counter`. As the name suggests, the prefix sum at index `i`, `prefix[i]`, equals the sum of the elements from index `0` through `i`:

\[ \text{prefix}[i] = \sum_{j=0}^i \text{counter[j]} \]

The prefix sum has a clear interpretation: `prefix[num] - 1` gives the index of the last occurrence of element `num` in the result array `res`. This information is crucial because it tells us where each element should be placed in the result array. Next, we traverse the original array `nums` in reverse, and for each element `num`, perform the following two steps.

1. Place `num` at index `prefix[num] - 1` of the array `res`.
2. Decrease the prefix sum `prefix[num]` by \(1\) to get the index for the next placement of `num`.

After the traversal is complete, the array `res` contains the sorted result, and finally `res` is used to overwrite the original array `nums`. The complete counting sort flow is shown in Figure 11-17.

<1><2><3><4><5><6><7><8>

Figure 11-17 Counting sort steps

The counting sort implementation is shown below:

Python C++Java C#Go Swift JS TS Dart Rust C Kotlin Ruby
counting_sort.py

    def counting_sort(nums: list[int]):
        """Counting sort"""
        # Complete implementation, can sort objects and is a stable sort
        # 1. Count the maximum element m in the array
        m = max(nums)
        # 2. Count the occurrence of each number
        # counter[num] represents the occurrence of num
        counter = [0] * (m + 1)
        for num in nums:
            counter[num] += 1
        # 3. Calculate the prefix sum of counter, converting "occurrence count" to "tail index"
        # counter[num]-1 is the last index where num appears in res
        for i in range(m):
            counter[i + 1] += counter[i]
        # 4. Traverse nums in reverse order, placing each element into the result array res
        # Initialize the array res to record results
        n = len(nums)
        res = [0] * n
        for i in range(n - 1, -1, -1):
            num = nums[i]
            res[counter[num] - 1] = num  # Place num at the corresponding index
            counter[num] -= 1  # Decrement the prefix sum by 1, getting the next index to place num
        # Use result array res to overwrite the original array nums
        for i in range(n):
            nums[i] = res[i]

counting_sort.cpp

    /* Counting sort */
    // Complete implementation, can sort objects and is a stable sort
    void countingSort(vector<int> &nums) {
        // 1. Count the maximum element m in the array
        int m = 0;
        for (int num : nums) {
            m = max(m, num);
        }
        // 2. Count the occurrence of each number
        // counter[num] represents the occurrence of num
        vector<int> counter(m + 1, 0);
        for (int num : nums) {
            counter[num]++;
        }
        // 3. Calculate the prefix sum of counter, converting "occurrence count" to "tail index"
        // counter[num]-1 is the last index where num appears in res
        for (int i = 0; i < m; i++) {
            counter[i + 1] += counter[i];
        }
        // 4. Traverse nums in reverse order, placing each element into the result array res
        // Initialize the array res to record results
        int n = nums.size();
        vector<int> res(n);
        for (int i = n - 1; i >= 0; i--) {
            int num = nums[i];
            res[counter[num] - 1] = num; // Place num at the corresponding index
            counter[num]--;              // Decrement the prefix sum by 1, getting the next index to place num
        }
        // Use result array res to overwrite the original array nums
        nums = res;
    }

counting_sort.java

    /* Counting sort */
    // Complete implementation, can sort objects and is a stable sort
    void countingSort(int[] nums) {
        // 1. Count the maximum element m in the array
        int m = 0;
        for (int num : nums) {
            m = Math.max(m, num);
        }
        // 2. Count the occurrence of each number
        // counter[num] represents the occurrence of num
        int[] counter = new int[m + 1];
        for (int num : nums) {
            counter[num]++;
        }
        // 3. Calculate the prefix sum of counter, converting "occurrence count" to "tail index"
        // counter[num]-1 is the last index where num appears in res
        for (int i = 0; i < m; i++) {
            counter[i + 1] += counter[i];
        }
        // 4. Traverse nums in reverse order, placing each element into the result array res
        // Initialize the array res to record results
        int n = nums.length;
        int[] res = new int[n];
        for (int i = n - 1; i >= 0; i--) {
            int num = nums[i];
            res[counter[num] - 1] = num; // Place num at the corresponding index
            counter[num]--; // Decrement the prefix sum by 1, getting the next index to place num
        }
        // Use result array res to overwrite the original array nums
        for (int i = 0; i < n; i++) {
            nums[i] = res[i];
        }
    }

counting_sort.cs

    /* Counting sort */
    // Complete implementation, can sort objects and is a stable sort
    void CountingSort(int[] nums) {
        // 1. Count the maximum element m in the array
        int m = 0;
        foreach (int num in nums) {
            m = Math.Max(m, num);
        }
        // 2. Count the occurrence of each number
        // counter[num] represents the occurrence of num
        int[] counter = new int[m + 1];
        foreach (int num in nums) {
            counter[num]++;
        }
        // 3. Calculate the prefix sum of counter, converting "occurrence count" to "tail index"
        // counter[num]-1 is the last index where num appears in res
        for (int i = 0; i < m; i++) {
            counter[i + 1] += counter[i];
        }
        // 4. Traverse nums in reverse order, placing each element into the result array res
        // Initialize the array res to record results
        int n = nums.Length;
        int[] res = new int[n];
        for (int i = n - 1; i >= 0; i--) {
            int num = nums[i];
            res[counter[num] - 1] = num; // Place num at the corresponding index
            counter[num]--; // Decrement the prefix sum by 1, getting the next index to place num
        }
        // Use result array res to overwrite the original array nums
        for (int i = 0; i < n; i++) {
            nums[i] = res[i];
        }
    }

counting_sort.go

    /* Counting sort */
    // Complete implementation, can sort objects and is a stable sort
    func countingSort(nums []int) {
        // 1. Count the maximum element m in the array
        m := 0
        for _, num := range nums {
            if num > m {
                m = num
            }
        }
        // 2. Count the occurrence of each number
        // counter[num] represents the occurrence of num
        counter := make([]int, m+1)
        for _, num := range nums {
            counter[num]++
        }
        // 3. Calculate the prefix sum of counter, converting "occurrence count" to "tail index"
        // counter[num]-1 is the last index where num appears in res
        for i := 0; i < m; i++ {
            counter[i+1] += counter[i]
        }
        // 4. Traverse nums in reverse order, placing each element into the result array res
        // Initialize the array res to record results
        n := len(nums)
        res := make([]int, n)
        for i := n - 1; i >= 0; i-- {
            num := nums[i]
            // Place num at the corresponding index
            res[counter[num]-1] = num
            // Decrement the prefix sum by 1, getting the next index to place num
            counter[num]--
        }
        // Use result array res to overwrite the original array nums
        copy(nums, res)
    }

counting_sort.swift

    /* Counting sort */
    // Complete implementation, can sort objects and is a stable sort
    func countingSort(nums: inout [Int]) {
        // 1. Count the maximum element m in the array
        let m = nums.max()!
        // 2. Count the occurrence of each number
        // counter[num] represents the occurrence of num
        var counter = Array(repeating: 0, count: m + 1)
        for num in nums {
            counter[num] += 1
        }
        // 3. Calculate the prefix sum of counter, converting "occurrence count" to "tail index"
        // counter[num]-1 is the last index where num appears in res
        for i in 0 ..< m {
            counter[i + 1] += counter[i]
        }
        // 4. Traverse nums in reverse order, placing each element into the result array res
        // Initialize the array res to record results
        var res = Array(repeating: 0, count: nums.count)
        for i in nums.indices.reversed() {
            let num = nums[i]
            res[counter[num] - 1] = num // Place num at the corresponding index
            counter[num] -= 1 // Decrement the prefix sum by 1, getting the next index to place num
        }
        // Use result array res to overwrite the original array nums
        for i in nums.indices {
            nums[i] = res[i]
        }
    }

counting_sort.js

    /* Counting sort */
    // Complete implementation, can sort objects and is a stable sort
    function countingSort(nums) {
        // 1. Count the maximum element m in the array
        let m = Math.max(...nums);
        // 2. Count the occurrence of each number
        // counter[num] represents the occurrence of num
        const counter = new Array(m + 1).fill(0);
        for (const num of nums) {
            counter[num]++;
        }
        // 3. Calculate the prefix sum of counter, converting "occurrence count" to "tail index"
        // counter[num]-1 is the last index where num appears in res
        for (let i = 0; i < m; i++) {
            counter[i + 1] += counter[i];
        }
        // 4. Traverse nums in reverse order, placing each element into the result array res
        // Initialize the array res to record results
        const n = nums.length;
        const res = new Array(n);
        for (let i = n - 1; i >= 0; i--) {
            const num = nums[i];
            res[counter[num] - 1] = num; // Place num at the corresponding index
            counter[num]--; // Decrement the prefix sum by 1, getting the next index to place num
        }
        // Use result array res to overwrite the original array nums
        for (let i = 0; i < n; i++) {
            nums[i] = res[i];
        }
    }

counting_sort.ts

    /* Counting sort */
    // Complete implementation, can sort objects and is a stable sort
    function countingSort(nums: number[]): void {
        // 1. Count the maximum element m in the array
        let m: number = Math.max(...nums);
        // 2. Count the occurrence of each number
        // counter[num] represents the occurrence of num
        const counter: number[] = new Array<number>(m + 1).fill(0);
        for (const num of nums) {
            counter[num]++;
        }
        // 3. Calculate the prefix sum of counter, converting "occurrence count" to "tail index"
        // counter[num]-1 is the last index where num appears in res
        for (let i = 0; i < m; i++) {
            counter[i + 1] += counter[i];
        }
        // 4. Traverse nums in reverse order, placing each element into the result array res
        // Initialize the array res to record results
        const n = nums.length;
        const res: number[] = new Array<number>(n);
        for (let i = n - 1; i >= 0; i--) {
            const num = nums[i];
            res[counter[num] - 1] = num; // Place num at the corresponding index
            counter[num]--; // Decrement the prefix sum by 1, getting the next index to place num
        }
        // Use result array res to overwrite the original array nums
        for (let i = 0; i < n; i++) {
            nums[i] = res[i];
        }
    }

counting_sort.dart

    /* Counting sort */
    // Complete implementation, can sort objects and is a stable sort
    void countingSort(List<int> nums) {
      // 1. Count the maximum element m in the array
      int m = 0;
      for (int _num in nums) {
        m = max(m, _num);
      }
      // 2. Count the occurrence of each number
      // counter[_num] represents occurrence count of _num
      List<int> counter = List.filled(m + 1, 0);
      for (int _num in nums) {
        counter[_num]++;
      }
      // 3. Calculate the prefix sum of counter, converting "occurrence count" to "tail index"
      // That is, counter[_num]-1 is the last occurrence index of _num in res
      for (int i = 0; i < m; i++) {
        counter[i + 1] += counter[i];
      }
      // 4. Traverse nums in reverse order, placing each element into the result array res
      // Initialize the array res to record results
      int n = nums.length;
      List<int> res = List.filled(n, 0);
      for (int i = n - 1; i >= 0; i--) {
        int _num = nums[i];
        res[counter[_num] - 1] = _num; // Place _num at corresponding index
        counter[_num]--; // Decrement prefix sum by 1 to get next placement index for _num
      }
      // Use result array res to overwrite the original array nums
      nums.setAll(0, res);
    }

counting_sort.rs

    /* Counting sort */
    // Complete implementation, can sort objects and is a stable sort
    fn counting_sort(nums: &mut [i32]) {
        // 1. Count the maximum element m in the array
        let m = *nums.iter().max().unwrap() as usize;
        // 2. Count the occurrence of each number
        // counter[num] represents the occurrence of num
        let mut counter = vec![0; m + 1];
        for &num in nums.iter() {
            counter[num as usize] += 1;
        }
        // 3. Calculate the prefix sum of counter, converting "occurrence count" to "tail index"
        // counter[num]-1 is the last index where num appears in res
        for i in 0..m {
            counter[i + 1] += counter[i];
        }
        // 4. Traverse nums in reverse order, placing each element into the result array res
        // Initialize the array res to record results
        let n = nums.len();
        let mut res = vec![0; n];
        for i in (0..n).rev() {
            let num = nums[i];
            res[counter[num as usize] - 1] = num; // Place num at the corresponding index
            counter[num as usize] -= 1; // Decrement the prefix sum by 1, getting the next index to place num
        }
        // Use result array res to overwrite the original array nums
        nums.copy_from_slice(&res)
    }

counting_sort.c

    /* Counting sort */
    // Complete implementation, can sort objects and is a stable sort
    void countingSort(int nums[], int size) {
        // 1. Count the maximum element m in the array
        int m = 0;
        for (int i = 0; i < size; i++) {
            if (nums[i] > m) {
                m = nums[i];
            }
        }
        // 2. Count the occurrence of each number
        // counter[num] represents the occurrence of num
        int *counter = calloc(m, sizeof(int));
        for (int i = 0; i < size; i++) {
            counter[nums[i]]++;
        }
        // 3. Calculate the prefix sum of counter, converting "occurrence count" to "tail index"
        // counter[num]-1 is the last index where num appears in res
        for (int i = 0; i < m; i++) {
            counter[i + 1] += counter[i];
        }
        // 4. Traverse nums in reverse order, placing each element into the result array res
        // Initialize the array res to record results
        int *res = malloc(sizeof(int) * size);
        for (int i = size - 1; i >= 0; i--) {
            int num = nums[i];
            res[counter[num] - 1] = num; // Place num at the corresponding index
            counter[num]--;              // Decrement the prefix sum by 1, getting the next index to place num
        }
        // Use result array res to overwrite the original array nums
        memcpy(nums, res, size * sizeof(int));
        // 5. Free memory
        free(res);
        free(counter);
    }

counting_sort.kt

    /* Counting sort */
    // Complete implementation, can sort objects and is a stable sort
    fun countingSort(nums: IntArray) {
        // 1. Count the maximum element m in the array
        var m = 0
        for (num in nums) {
            m = max(m, num)
        }
        // 2. Count the occurrence of each number
        // counter[num] represents the occurrence of num
        val counter = IntArray(m + 1)
        for (num in nums) {
            counter[num]++
        }
        // 3. Calculate the prefix sum of counter, converting "occurrence count" to "tail index"
        // counter[num]-1 is the last index where num appears in res
        for (i in 0..<m) {
            counter[i + 1] += counter[i]
        }
        // 4. Traverse nums in reverse order, placing each element into the result array res
        // Initialize the array res to record results
        val n = nums.size
        val res = IntArray(n)
        for (i in n - 1 downTo 0) {
            val num = nums[i]
            res[counter[num] - 1] = num // Place num at the corresponding index
            counter[num]-- // Decrement the prefix sum by 1, getting the next index to place num
        }
        // Use result array res to overwrite the original array nums
        for (i in 0..<n) {
            nums[i] = res[i]
        }
    }

counting_sort.rb

    ### Counting sort ###
    def counting_sort(nums)
      # Complete implementation, can sort objects and is a stable sort
      # 1. Count the maximum element m in the array
      m = nums.max
      # 2. Count the occurrence of each number
      # counter[num] represents the occurrence of num
      counter = Array.new(m + 1, 0)
      nums.each { |num| counter[num] += 1 }
      # 3. Calculate the prefix sum of counter, converting "occurrence count" to "tail index"
      # counter[num]-1 is the last index where num appears in res
      (0...m).each { |i| counter[i + 1] += counter[i] }
      # 4. Traverse nums in reverse, fill elements into result array res
      # Initialize the array res to record results
      n = nums.length
      res = Array.new(n, 0)
      (n - 1).downto(0).each do |i|
        num = nums[i]
        res[counter[num] - 1] = num # Place num at the corresponding index
        counter[num] -= 1 # Decrement the prefix sum by 1, getting the next index to place num
      end
      # Use result array res to overwrite the original array nums
      (0...n).each { |i| nums[i] = res[i] }
    end

## 11.9.3 Algorithm Characteristics

- Time complexity is \(O(n + m)\), and counting sort is non-adaptive: Traversing `nums` and `counter` both takes linear time. In general, when \(n \gg m\), the time complexity approaches \(O(n)\).
- Space complexity of \(O(n + m)\), non-in-place sorting: Uses arrays `res` and `counter` of lengths \(n\) and \(m\) respectively.
- Stable sorting: Since elements are filled into `res` in a "right-to-left" order, traversing `nums` in reverse can avoid changing the relative positions of equal elements, thereby achieving stable sorting. In fact, traversing `nums` in forward order can also yield correct sorting results, but the result would be unstable.

## 11.9.4 Limitations

At this point, you might think counting sort is quite ingenious because it achieves efficient sorting simply by counting occurrences. However, the prerequisites for using counting sort are fairly restrictive.

Counting sort is only applicable to non-negative integers. To apply it to other types of data, you must ensure that they can be converted to non-negative integers without changing the relative ordering of the elements. For example, for an integer array containing negative numbers, you can first add a constant to every number to shift them into the non-negative range, and then shift them back after sorting.

Counting sort is well suited to cases with many elements but a small value range. For example, in the above scenario, \(m\) cannot be too large; otherwise, it consumes too much space. And when \(n \ll m\), counting sort takes \(O(m)\) time, which may be slower than sorting algorithms with \(O(n \log n)\) time complexity.

##### Feel free to drop your insights, questions or suggestions