Count Sort
Understand the count sort algorithm, which sorts integers by counting occurrences and using prefix sums for positioning. This lesson explains its three phases, stability, time and space complexity, and appropriate use cases, helping you apply count sort effectively for bounded integer arrays.
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] ...