A non-comparison sorting algorithm that counts the occurrences of distinct key values to reconstruct a sorted array.
Parameters
15
9
Visualization
Step: 0
1. Main Array
2. Frequency Count Array (Size: K + 1)
Click Step or Auto-Run to begin counting sort.
Algorithm Insight
Counting Sort is a Non-Comparison sorting algorithm, great when the range of inputs ($K$) is small compared to the array size ($N$).
1.Initialize a Count Array of size $K+1$ with zeros.
2.Iterate the main array. Increment Count[value] for each element read.
3.Iterate the Count Array. Overwrite the main array sequentially with valid elements.
Efficiency
Time ComplexityO(N + K)
Space ComplexityO(K)
Deconstructing Counting Sort
How this unique non-comparison algorithm sorts integers in linear time.
Quick Context: What is Counting Sort?
Counting Sort is a special type of sorting algorithm that doesn't work by comparing elements. Instead, it sorts integers by counting the number of times each distinct value appears in the input array. It's extremely fast, but it only works when the input values are integers within a specific, relatively small range.
The Core Idea: Counting Frequencies
The algorithm operates in three main phases, as shown in the visualizer:
1. Counting Phase: Create a "frequency count" array (the bottom array in the visualizer). Iterate through the main array. For each element you read, use its value as an index into the frequency array and increment the count at that index. After this phase, `frequency_array[i]` will store how many times the number `i` appeared in the input.
2. (Optional) Cumulative Sum: A more advanced version of Counting Sort modifies the frequency array to store the cumulative sum of counts. This tells you the final sorted position of each element. Our visualizer uses a simpler approach for clarity.
3. Reconstruction Phase: Iterate through the frequency count array. For each index `i`, read its count `c`. Then, write the value `i` into the main array `c` times. By the end, the main array is overwritten with the sorted elements.
Guided Experiments with the Visualizer
The Counting Phase: Click "Randomize" and then "Next Step" repeatedly. Watch as the algorithm reads a value from the top array (highlighted in blue). Then, see how the corresponding bar in the bottom "Frequency Count" array grows (highlighted in yellow). This directly maps each value to its count.
The Reconstruction Phase: Once all top bars have been read, the algorithm switches to writing. It will start from the beginning of the frequency array. If it finds a count greater than zero, it writes that index value back into the main array (highlighted in green) and decrements the count.
The 'K' Parameter: Use the "Max Value Limit (K)" slider. Set it to a low value (e.g., 5). Notice the frequency array becomes smaller. Now set it to a high value (e.g., 15). The frequency array grows. This demonstrates the algorithm's dependency on the range of input values. If K is very large, the frequency array becomes huge, consuming a lot of memory.
Pseudocode
// Simplified Counting Sort
function countingSort(array, k) {
counts = new Array(k + 1).fill(0);
output_pos = 0;
// 1. Count frequencies
for (value in array) {
counts[value]++;
}
// 2. Reconstruct the array
for (value from 0 to k) {
for (i from 0 to counts[value]) {
array[output_pos] = value;
output_pos++;
}
}
}
Performance & Limitations
Counting Sort is incredibly fast with a time complexity of O(n + k), where 'n' is the number of elements and 'k' is the range of the input values. This is linear time, much faster than comparison-based sorts like Merge Sort or Quick Sort (O(n log n)).
However, its major limitation is its space complexity of O(k). If you need to sort a few numbers but their values can be very large (e.g., up to 1,000,000), you would need a frequency array with a million elements, which is often impractical. It's best used when 'k' is not significantly larger than 'n'.
Cheat sheet
Counting Sort
Counting Sort is a special type of sorting algorithm that doesn't work by comparing elements. Instead, it sorts integers by counting the number of times each distinct value appears in the input array. It's extremely fast, but it only works when the input values are integers within a specific, relatively small range.