Counting Sort non-comparison algorithm explained: frequency array tally, cumulative prefix sum positioning, offset handling for negative numbers, stability preservation, and JavaScript code.
Counting Sort is a non-comparison integer sorting algorithm that beats the theoretical O(n log n) lower bound for comparison sorts. Rather than comparing elements directly against one another, it determines the position of each element by tallying the frequency of each unique key in a count array and calculating cumulative prefix sums.
Because it runs in O(n + k) time (where n is the number of elements and k is the difference between the maximum and minimum key values), Counting Sort achieves O(n) linear performance whenever the range k is proportional to n (k = O(n)). Furthermore, by scanning the original array from right to left during output assembly, Counting Sort strictly preserves stability.
Find the minimum and maximum values in the input array to determine the frequency table size (range = max - min + 1) and calculate the offset.
Initialize a count array of size (range) with zeros. Loop through the input array and increment count[num - min] for each element.
Transform the count array into cumulative prefix sums: count[i] += count[i - 1]. Each entry now indicates the 1-based ending index for that key.
Iterate through the original array backwards (from index n - 1 down to 0). Place each value at output[count[val - min] - 1] and decrement count[val - min].
1function countingSort(arr) {2 if (arr.length <= 1) return arr;3 4 let min = arr[0];5 let max = arr[0];6 7 // 1. Find min and max values to handle negative numbers & arbitrary ranges8 for (let i = 1; i < arr.length; i++) {9 if (arr[i] < min) min = arr[i];10 if (arr[i] > max) max = arr[i];11 }12 13 const range = max - min + 1;14 const count = new Array(range).fill(0);15 const output = new Array(arr.length);16 17 // 2. Tally frequencies18 for (let i = 0; i < arr.length; i++) {19 count[arr[i] - min]++;20 }21 22 // 3. Accumulate prefix sums23 for (let i = 1; i < range; i++) {24 count[i] += count[i - 1];25 }26 27 // 4. Build output array in reverse to preserve stability28 for (let i = arr.length - 1; i >= 0; i--) {29 const val = arr[i];30 const idx = count[val - min] - 1;31 output[idx] = val;32 count[val - min]--;33 }34 35 return output;36}37 38// Example usage:39// countingSort([4, -2, 2, 8, 3, -2, 1]); // [-2, -2, 1, 2, 3, 4, 8]Play through every comparison, swap, and state change, adjust the speed, or enter custom inputs to test edge cases.
The full interactive roadmap is unlocking — these specialized modules land in upcoming releases.
This feature will be implemented in the next update.
This feature will be implemented in the next update.
This feature will be implemented in the next update.
Explore the full catalog — 30+ algorithms with more unlocking every release.
Ready — press Play or use step controls to walk through the algorithm.
Comparisons
0
Swaps / Shifts
0
Passes / Depth
0
Elements
10
Test your understanding of Counting Sort complexity and step mechanics.
Q1.When is Counting Sort preferred over Comparison-based sorts like Quick Sort or Merge Sort?
Q2.Why does Counting Sort iterate through the input array in reverse order when building the output array?
Apply Counting Sort to real coding interview questions.
Sort an array with red, white, and blue objects (values 0, 1, and 2).