Algorithm Overview

1. Identify the maximum value, max_value, in the input array.
2. Create a count array called count, sized max_value + 1, initializing all elements to 0.
3. Traverse the input array to tally the frequency of each element by incrementing its corresponding index in the count array.
4. Compute the cumulative sum in the count array, ensuring that each count represents the number of elements less than or equal to that index.
5. Initialize an output array of the same size as the input array, filled with zeros.
6. Iterate through the input array in reverse order. For each element, determine its correct position in the output array by referencing the count array, then decrement the count for that element.
7. Repeat the previous step until all elements have been placed into the output array.
8. Transfer the sorted elements from the output array back to the original input array.

After completing these steps, the input array will be sorted in non-decreasing order.

Visualization

While it might seem complex at first glance, the process is straightforward. Let's break down the visualization into steps:

1. Count Occurrences: First, tally how many times each value appears in the array.
2. Cumulative Sum: Modify the count array to reflect cumulative sums, allowing us to determine the final position of each element in the sorted output.
3. Identify Positions: For each element in the count array, add the value of the previous index to it, generating a running total of how many elements are less than or equal to the current value.
4. Place Elements: Use the element's value to find its index in the count array, which now indicates the correct position for the element in the output array. After placing the element, decrement the count for that value.

The steps can be illustrated as follows:

• Initial Array: [4, 2, 2, 8, 3, 3, 1]
• Step 1: Count occurrences
• Step 2: Calculate cumulative sums
• Step 3: Determine positions
• Step 4: Place elements correctly
• Step 5: Final sorted array: [1, 2, 2, 3, 3, 4, 8]

Code Implementation

def counting_sort(array: list[int]) -> None:

max_value = max(array) # Identify the maximum value

count = [0] * (max_value + 1) # Create count array

for num in array:

count[num] += 1 # Tally occurrences

size = len(count) # Size of the count array

output = [0] * len(array) # Output array for sorted items

for i in range(1, size):

count[i] += count[i - 1] # Compute cumulative sum

i = len(array) - 1

while i >= 0:

current = count[array[i]] - 1 # Determine correct position

output[current] = array[i] # Place item in output

count[array[i]] -= 1 # Decrement count

i -= 1

for i in range(0, len(array)):

array[i] = output[i] # Copy sorted items back

array = [4, 2, 2, 8, 3, 3, 1]

counting_sort(array)

print(array) # Output: [1, 2, 2, 3, 3, 4, 8]

Time Complexity

• Best: O(n + k)
• Average: O(n + k)
• Worst: O(n + k)

Space Complexity

• O(max)

Where:

• n represents the size of the array to be sorted.
• k is the maximum value present in the input array.
• max indicates the highest value among the input elements, determining the size of the count array as max + 1 to accommodate all possible values from 0 to max.