Counting Sort: Stability
You'll learn why counting sort preserves the order of equal elements and when this property matters.
What Does Stability Mean?
Recall that a sorting algorithm is stable if it maintains the relative order of elements with equal keys. When two items have the same value, a stable sort ensures the one that appeared first in the input remains first in the output.
Why Counting Sort Is Stable
Counting sort achieves stability through how it places elements in the output array. The algorithm builds its cumulative count array to determine positions, then iterates backward through the input. When it encounters an element, it:
- Looks up the position from the count array
- Places the element at that position
- Decrements the count for that value
The backward traversal is key: If two elements have the same value, the one appearing later in the input is processed first and placed at the rightmost available position for that value. When the earlier element is processed, it takes the next available position to the left.
Why This Matters
Stability becomes critical when sorting complex objects by one field while preserving order from a previous sort. For example, if you've sorted student records by name and then sort by grade, a stable sort keeps students with the same grade alphabetized.
In radix sort (which applies counting sort digit-by-digit), stability is essential for correctness. Without it, the final result would be wrong because earlier digit orderings would be destroyed.
Key Takeaway: Counting sort is stable because it processes input elements backward, ensuring that equal values maintain their original relative order—a property crucial for multi-key sorting and radix sort correctness.