Counting Sort is a simple and intuitive non-comparison sorting algorithm. It determines the position of elements in the sorted array by counting the occurrences of each element and then using these counts. This algorithm is highly efficient when the element range is small and there are many repeated elements, making it ideal for beginners to understand and implement.

Core Algorithm Idea¶

1. Determine Element Range: Find the minimum value min and maximum value max in the array to define the element range as [min, max].
2. Count Element Frequencies: Create a count array with length max - min + 1 to record the frequency of each element.
3. Compute Prefix Sums: Convert the count array into a prefix sum array, where each value at position i indicates the last position of the element min + i in the sorted array.
4. Generate Sorted Result: Traverse the original array from the end to place elements into the result array based on their mapped positions and prefix sums, ensuring stability.

Code Implementation Steps¶

1. Handle Edge Cases¶

If the array is empty or has only one element, return immediately as no sorting is needed.

2. Determine Element Range¶

Traverse the array to find the minimum min and maximum max values, then calculate the range size as max - min + 1.

3. Count Element Frequencies¶

Create a count array of length max - min + 1. For each element num in the original array, increment count[num - min] (mapping to non-negative indices to avoid negative values).

4. Compute Prefix Sums¶

Accumulate the count array to determine the last position of each element in the sorted array.

5. Generate Sorted Result¶

Traverse the original array from the end. For each element num, place it in the result array at position count[num - min] - 1, then decrement the count to maintain stability for repeated elements.

Java Code Implementation¶

import java.util.Arrays;

public class CountingSort {

    public static void countingSort(int[] arr) {
        // Edge case handling: no sorting needed for empty or single-element array
        if (arr == null || arr.length <= 1) {
            return;
        }

        // Step 1: Find the minimum and maximum values in the array
        int min = arr[0];
        int max = arr[0];
        for (int num : arr) {
            if (num < min) min = num;
            if (num > max) max = num;
        }

        // Step 2: Create a count array with length (max - min + 1)
        int[] count = new int[max - min + 1];

        // Step 3: Count occurrences of each element
        for (int num : arr) {
            count[num - min]++; // Map elements to non-negative indices
        }

        // Step 4: Compute prefix sums to determine the last position of each element
        for (int i = 1; i < count.length; i++) {
            count[i] += count[i - 1];
        }

        // Step 5: Generate the sorted result array (traverse from the end to ensure stability)
        int[] result = new int[arr.length];
        for (int i = arr.length - 1; i >= 0; i--) {
            int num = arr[i];
            int k = num - min; // Index in the count array
            result[count[k] - 1] = num; // Place the element in the correct position
            count[k]--; // Decrement count for subsequent duplicates
        }

        // Copy the result back to the original array
        System.arraycopy(result, 0, arr, 0, arr.length);
    }

    // Test code
    public static void main(String[] args) {
        int[] arr = {4, 2, 2, 8, 3, 3, 1};
        System.out.println("Before sorting: " + Arrays.toString(arr));
        countingSort(arr);
        System.out.println("After sorting: " + Arrays.toString(arr));
    }
}

Code Explanation¶

• Frequency Counting: Mapping elements using num - min ensures non-negative indices, avoiding negative index issues. For example, element 2 with min=1 maps to index 1 (2-1=1).
• Prefix Sum Calculation: The accumulated count array gives the last position of each element. For [1,2,2,3,3,4,8] with min=1, the prefix sum array is [1,3,5,6,6,6,6,7], where count[2]=5 means element 3 (i.e., min+2=3) ends at position 4 (5-1).
• Stability: Traversing from the end preserves the relative order of duplicates. For example, two 2s in the original array will be placed in positions 1 and 2 of the result array in their original order.

Complexity Analysis¶

• Time Complexity: O(n + k), where n is the array length and k is the element range (max - min + 1). The algorithm runs in three linear passes: counting, prefix sum calculation, and result generation.
• Space Complexity: O(n + k), due to the additional count and result arrays.

Applicable Scenarios¶

• Elements are integers with a small range (e.g., student scores, ages).
• Repeated elements are frequent, and relative order preservation (stability) is required.

Counting Sort achieves sorting through simple counting and summation operations without complex comparison logic, making it an excellent introduction to sorting algorithms for beginners.