Counting Sort is a simple and efficient sorting algorithm that belongs to the non-comparison-based sorting category. It is particularly suitable for sorting integers, especially when the value range of the data is not large. Compared to comparison-based sorting algorithms like Bubble Sort or Selection Sort, Counting Sort determines the final position of elements by counting their occurrences, achieving a linear time complexity (O(n + k), where n is the number of elements to be sorted and k is the range of the data values).

Basic Idea¶

1. Determine Data Range: First, find the minimum and maximum values in the unsorted array to define the range of elements to be counted, avoiding the creation of an excessively large count array.
2. Count Element Occurrences: Create a count array with a length of (max - min + 1) to record the frequency of each element.
3. Construct Sorted Result: Based on the count array, output each element in order from the minimum value, with the number of outputs equal to the frequency of the element recorded in the count array.

Example Demonstration¶

Take the array [4, 2, 2, 8, 3, 3, 1] to demonstrate the counting sort process:

1. Determine Data Range: The minimum value is 1 and the maximum value is 8, so the data range is 1~8, and the count array length is 8 - 1 + 1 = 8.
2. Count Element Frequencies: Traverse the original array to count occurrences of each element:
   - Element 1 occurs 1 time
   - Element 2 occurs 2 times
   - Element 3 occurs 2 times
   - Element 4 occurs 1 time
   - Element 8 occurs 1 time
   - Other elements (5, 6, 7) occur 0 times
   Thus, the count array is [1, 2, 2, 1, 0, 0, 0, 1] (indices 0~7 correspond to the frequencies of 1~8).
3. Construct Sorted Result: Output elements in order from the minimum value 1, with counts determined by the count array:
   - Output 1 once → [1]
   - Output 2 twice → [1, 2, 2]
   - Output 3 twice → [1, 2, 2, 3, 3]
   - Output 4 once → [1, 2, 2, 3, 3, 4]
   - Output 8 once → [1, 2, 2, 3, 3, 4, 8]

Python Implementation¶

def counting_sort(arr):
    # Handle empty array or single-element array (no sorting needed)
    if not arr:
        return []
    if len(arr) == 1:
        return arr

    # Step 1: Determine minimum and maximum values
    min_val = min(arr)
    max_val = max(arr)

    # Step 2: Create count array (length = max - min + 1, initialized to 0)
    count_size = max_val - min_val + 1
    count = [0] * count_size

    # Step 3: Count occurrences of each element
    for num in arr:
        # Calculate index in count array (element value - min_val)
        index = num - min_val
        count[index] += 1  # Increment count for the element

    # Step 4: Generate sorted result based on count array
    sorted_arr = []
    for i in range(count_size):
        # Current element value = min_val + index
        num = min_val + i
        # Add the element count[i] times to the result
        sorted_arr.extend([num] * count[i])

    return sorted_arr

Code Explanation¶

• Boundary Handling: If the input array is empty or has only one element, return the original array directly (no sorting required).
• Data Range Determination: Use min() and max() to get the minimum and maximum values, avoiding an overly large count array.
• Count Array Construction: Length is max_val - min_val + 1 to cover all possible elements.
• Frequency Counting: Traverse the original array, compute the index in the count array as num - min_val, and increment the count for that index.
• Result Generation: Output elements in order from the minimum value, with the number of repetitions determined by the count array.

Applicable Scenarios and Characteristics¶

• Applicable Scenarios: Data consists of integers with a small value range (e.g., exam scores, ages) or contains many duplicate elements.
• Stability: Counting sort is stable (the relative order of equal elements is preserved), as duplicates are output in their original order.
• Memory Usage: If the data range is too large (e.g., max >> min), the count array will consume significant memory, making it unsuitable in such cases.

Test Examples¶

# Test Case 1: Basic integer array
arr1 = [4, 2, 2, 8, 3, 3, 1]
print(counting_sort(arr1))  # Output: [1, 2, 2, 3, 3, 4, 8]

# Test Case 2: Array containing negative numbers
arr2 = [-3, 1, 2, -3, 0]
print(counting_sort(arr2))  # Output: [-3, -3, 0, 1, 2]

Through the above steps, counting sort efficiently sorts integer arrays, especially suitable for scenarios with a small data range and many duplicate elements.