Counting Sort

Counting sort is a non-comparative integer sorting algorithm, particularly suitable for situations where the range of elements to be sorted (the difference between the maximum and minimum values) is not large, but the number of elements is large. Its core idea is to count the occurrences of each integer and then directly calculate the position of each element in the sorted array.

Basic Idea and Applicable Conditions

• The input data must be integers, and the range must be known (or can be determined by traversal)
• Time complexity is O(n+k), where n is the number of elements and k is the size of the integer range
• When k=O(n), the algorithm is very efficient; but when k is much larger than n, space is wasted severely

Detailed Algorithm Steps

Step 1: Determine the Range
First, traverse the entire array to find the maximum value max and the minimum value min, and calculate the range size k = max - min + 1

Example: Array [4,2,2,8,3,3,1]

• min = 1, max = 8
• k = 8 - 1 + 1 = 8

Step 2: Create the Count Array
Create a count array count of length k, with all initial values set to 0

• count[i] will be used to store the number of occurrences of the value (min+i)

Example: The length of the count array is 8, index 0 corresponds to value 1, index 7 corresponds to value 8

Step 3: Count Occurrences
Traverse the original array. For each element x, calculate its index in the count array: index = x - min
Then increment the value of count[index] by 1

Example counting process:

• Element 4: index = 4-1 = 3 → count[3]++
• Element 2: index = 2-1 = 1 → count[1]++
• Element 2: index = 1 → count[1]++
• Element 8: index = 8-1 = 7 → count[7]++
• Element 3: index = 3-1 = 2 → count[2]++
• Element 3: index = 2 → count[2]++
• Element 1: index = 1-1 = 0 → count[0]++

Final count array: [1,2,2,1,0,0,0,1]
Meaning: Value 1 appears 1 time, value 2 appears 2 times, value 3 appears 2 times, value 4 appears 1 time, value 8 appears 1 time

Step 4: Calculate Cumulative Frequencies (Key Step)
Convert the count array into a cumulative frequency array, so that count[i] represents the total number of elements less than or equal to (min+i)
Method: Starting from index 1, add each count[i] to the previous count[i-1]

Calculation process:

• count[0] = 1 (remains unchanged)
• count[1] = 1+2 = 3
• count[2] = 3+2 = 5
• count[3] = 5+1 = 6
• count[4] = 6+0 = 6
• count[5] = 6+0 = 6
• count[6] = 6+0 = 6
• count[7] = 6+1 = 7

Cumulative frequency array: [1,3,5,6,6,6,6,7]
Meaning: There are 1 element ≤1, 3 elements ≤2, 5 elements ≤3, 6 elements ≤4, and 7 elements ≤8

Step 5: Fill the Result Array Backwards
Create a result array of the same length as the original array
Traverse the original array from the end to the beginning (to ensure stability):

• For each element x, calculate index = x - min
• In the result array, the position of this element should be count[index] - 1
• Place x at that position in the result array, then decrement count[index] by 1

Filling process (starting from the end of the original array):

1. Element 1: index=0, position=count[0]-1=1-1=0 → result[0]=1, count[0]=0
2. Element 3: index=2, position=count[2]-1=5-1=4 → result[4]=3, count[2]=4
3. Element 3: index=2, position=4-1=3 → result[3]=3, count[2]=3
4. Element 8: index=7, position=count[7]-1=7-1=6 → result[6]=8, count[7]=6
5. Element 2: index=1, position=count[1]-1=3-1=2 → result[2]=2, count[1]=2
6. Element 2: index=1, position=2-1=1 → result[1]=2, count[1]=1
7. Element 4: index=3, position=count[3]-1=6-1=5 → result[5]=4, count[3]=5

Final sorted result: [1,2,2,3,3,4,8]

Algorithm Characteristics Analysis

• Stability: Achieved by filling backwards, ensuring the relative order of equal elements remains unchanged
• Space Complexity: O(k) for the count array, O(n) for the result array, total space O(n+k)
• Limitations: Only applicable to integer sorting; inefficient when k is large

Counting sort is the foundation for bucket sort and radix sort. Understanding it helps in mastering more complex non-comparative sorting algorithms.