Counting sort is a non-comparison-based sorting algorithm that works by counting the occurrences of each distinct element in the input array. It is particularly efficient for sorting integers or objects that can be mapped to a finite range of integer keys. The basic idea is to determine the number of occurrences of each value in the input, and then use this information to place those values in their correct positions in the output array. ### How Counting Sort Works 1.
Articles by others on the same topic
Counting sort uses integer sort keys in directly as indices into an array of counts. Constant-cost counting and indexing give time complexity in Big O notation. To retain complete sorting records, cumulative counts locate their output ranges; filling each range from its end while scanning the input backwards gives stable sorting. Emitting bare sort keys from counts would discard associated data. The term matters when the key range is large.[ref]
11.2 Counting Sort and Radix Sort. Open Data Structures: An Introduction by Pat Morin; Theorem 11.7 and stability
For an original worked example, take complete sorting records and possible integer sort keys:The letters label the associated data, and are never compared. Both input and output array indices start at zero, so their valid positions are ; the count array has array indices . Stable sorting must produceThe equal-sort key groups retain and in arrival order. Counting sort prefix ranges explain where those groups belong; stable record placement in counting sort explains how to fill them without losing that order or the complete sorting records.