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]
Articles by others on the same topic
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.