What is Counting Sort?¶

Counting Sort is a non-comparison-based sorting algorithm. Its core idea is to count the occurrences of each element and then directly construct the sorted array based on these counts. Unlike comparison-based algorithms like Quick Sort or Merge Sort, Counting Sort does not require comparing element sizes. Instead, it uses a “counting” approach to sort elements. This algorithm is particularly suitable for scenarios where the range of integers is not large, such as student scores (0-100) or ages (0-150).

Basic Idea¶

Let’s use a concrete example to illustrate the steps of Counting Sort. Suppose we want to sort the array [4, 2, 2, 8, 3, 3, 1].

1. Count Element Frequencies:
   First, find the maximum value in the array (here, it is 8). Create a count array count with size max_val + 1 to record the frequency of each element. Traverse the original array to count occurrences:
   - count[0] = 0 (no 0s)
   - count[1] = 1 (element 1 appears once)
   - count[2] = 2 (element 2 appears twice)
   - count[3] = 2 (element 3 appears twice)
   - count[4] = 1 (element 4 appears once)
   - count[5] = 0 (no 5s)
   - count[6] = 0 (no 6s)
   - count[7] = 0 (no 7s)
   - count[8] = 1 (element 8 appears once)

2. Construct the Sorted Array:
   Based on the frequency counts, insert elements into the result array in order:
   - Element 1 (1 occurrence) → Result: [1]
   - Element 2 (2 occurrences) → Result: [1, 2, 2]
   - Element 3 (2 occurrences) → Result: [1, 2, 2, 3, 3]
   - Element 4 (1 occurrence) → Result: [1, 2, 2, 3, 3, 4]
   - Element 8 (1 occurrence) → Result: [1, 2, 2, 3, 3, 4, 8]

C++ Code Implementation¶

Here is the complete C++ implementation of Counting Sort:

#include <iostream>
using namespace std;

// Counting Sort function: sorts array arr
void countingSort(int arr[], int n) {
    // Step 1: Find the maximum value in the array
    int max_val = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] > max_val) {
            max_val = arr[i];
        }
    }

    // Step 2: Create a count array with size max_val + 1, initialized to 0
    int count[max_val + 1] = {0};

    // Step 3: Count the occurrences of each element
    for (int i = 0; i < n; i++) {
        count[arr[i]]++;
    }

    // Step 4: Construct the sorted array
    int output[n]; // Result array
    int index = 0; // Current index of the result array
    for (int i = 0; i <= max_val; i++) {
        // Insert element i count[i] times into the result array
        while (count[i] > 0) {
            output[index] = i;
            index++;
            count[i]--;
        }
    }

    // Step 5: Copy the sorted result back to the original array
    for (int i = 0; i < n; i++) {
        arr[i] = output[i];
    }
}

// Test function
int main() {
    int arr[] = {4, 2, 2, 8, 3, 3, 1};
    int n = sizeof(arr) / sizeof(arr[0]);

    cout << "Array before sorting: ";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }

    countingSort(arr, n);

    cout << "\nArray after sorting: ";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;

    return 0;
}

Code Explanation¶

1. Find Maximum Value: Traverse the array to determine the maximum element, which is used to size the count array.
2. Count Frequencies: The count array records how many times each element appears (e.g., count[2] = 2 means element 2 appears twice).
3. Build Result Array: Traverse the count array and insert each element into the result array output as many times as it appears.
4. Copy Back to Original Array: Transfer the sorted result from output back to the original array arr.

Time and Space Complexity¶

• Time Complexity: O(n + k), where n is the array length and k is the range of values (max - min). Traversing the array to count takes O(n), and constructing the result takes O(n), resulting in O(n + k) total time.
• Space Complexity: O(k), as we need additional arrays count and output whose sizes depend on the maximum value k.

Applicable Scenarios and Considerations¶

• Applicable Scenarios:
• Elements are non-negative integers with a small range (e.g., student scores, ages).

• Requires efficient sorting and does not care about the relative order of equal elements (stable sorting requires additional handling).

• Handling Negative Numbers: For arrays with negative values, use an offset to convert negatives to non-negatives. For example, for [-1, 3, -2], add the minimum value (offset = 2) to get [1, 5, 0], sort, then subtract the offset.

By following these steps, Counting Sort achieves linear time complexity and is an efficient algorithm for sorting small-range integers. Beginners only need to understand the core logic of “count frequencies → build result” to quickly master its implementation.