Count Sort
Explore the Count Sort algorithm, which sorts integer arrays by counting occurrences and using prefix sums to place elements without comparisons. Understand its phases, stability, and when to apply it for efficient sorting in JavaScript.
A teacher has just finished grading 30 exam papers. Every mark is a whole number between 0 and 10. She needs to arrange the papers in order of score.
She could use any comparison-based algorithm, but she spots a faster approach. She takes 11 empty trays, labels them from 0 to 10, and places each paper in the tray corresponding to its score. When she is done, she simply collects the trays in order: all the 0s first, then the 1s, then the 2s, and so on. The papers are now sorted.
She never compares one papers score with another. Instead, she uses each score as a direct address, telling her exactly which tray it belongs in. This is the core idea behind count sort.
Count sort is a non-comparison-based sorting algorithm that sorts integers by counting the occurrences of each distinct value and using those counts, along with prefix sums, to place each element into its correct position in the output array.
Why can it beat O(n log n):
The comparison-based lower bound proves that no algorithm using only comparisons can sort faster than O(n log n) in the worst case. Count sort avoids this limitation because it does not compare elements. Instead, it uses the values themselves as indices into an auxiliary array. This approach works only when the values are bounded integers within a known range.
How count sort works
Count Sort runs in three distinct phases. Each phase has a clear purpose, and together they produce a sorted, stable output.
Phase 1: Count occurrences
Create a count array of size k + 1, where k is the maximum value in the input. Initialize all elements of the count array to 0. Scan the input array once. For each element, increment the corresponding index in the count array. After this phase, count[v] stores how many times the value v appears in the input.
Phase 2: Compute prefix sums
Transform the count array into a prefix sum array. For each index i, update:
count[i] = count[i] + count[i - 1]
After this phase, count[v] stores how many elements are less than or equal to v. This tells us the final position range of each value and the exact index where the last occurrence of v should be placed.
Phase 3: Reconstruct the output
Scan the input array from right to left. For each element v:
Place it at index
count[v] - 1in the output array.Decrement
count[v]by 1.
Scanning from right to left ensures that equal elements retain their original relative order, making the algorithm stable. ...