Editing Counting sort (section)

{{Short description|Sorting algorithm}}
{{Infobox algorithm|class=[[Sorting Algorithm]]|data=[[Array data structure|Array]]|time=<math>O(n+k)</math>, where k is the range of the non-negative key values.|space=<math>O(n+k)</math>}}

In [[computer science]], '''counting sort''' is an [[algorithm]] for [[sorting algorithm|sorting]] a collection of objects according to keys that are small positive [[integer]]s; that is, it is an [[integer sorting]] algorithm. It operates by counting the number of objects that possess distinct key values, and applying prefix sum on those counts to determine the positions of each key value in the output sequence. Its running time is linear in the number of items and the difference between the maximum key value and the minimum key value, so it is only suitable for direct use in situations where the variation in keys is not significantly greater than the number of items. It is often used as a subroutine in [[radix sort]], another sorting algorithm, which can handle larger keys more efficiently.<ref name="clrs">{{citation
 | last1 = Cormen | first1 = Thomas H. | author1-link = Thomas H. Cormen
 | last2 = Leiserson | first2 = Charles E. | author2-link = Charles E. Leiserson
 | last3 = Rivest | first3 = Ronald L. | author3-link = Ron Rivest
 | last4 = Stein | first4 = Clifford | author4-link = Clifford Stein
 | contribution = 8.2 Counting Sort
 | edition = 2nd
 | isbn = 0-262-03293-7
 | pages = 168–170
 | publisher = [[MIT Press]] and [[McGraw-Hill]]
 | title = [[Introduction to Algorithms]]
 | year = 2001}}. See also the historical notes on page 181.</ref><ref name="edmonds">{{citation|first=Jeff|last=Edmonds|contribution=5.2 Counting Sort (a Stable Sort)|pages=72–75|title=How to Think about Algorithms|publisher=Cambridge University Press|year=2008|isbn=978-0-521-84931-9}}.</ref><ref name="sedgewick">{{citation|first=Robert|last=Sedgewick|author-link=Robert Sedgewick (computer scientist)|contribution=6.10 Key-Indexed Counting|title=Algorithms in Java, Parts 1-4: Fundamentals, Data Structures, Sorting, and Searching|edition=3rd|publisher=Addison-Wesley|year=2003|pages=312–314}}.</ref>

Counting sort is not a [[comparison sort]]; it uses key values as indexes into an array and the {{math|[[Big O notation#Family of Bachmann–Landau notations|Ω]](''n'' log ''n'')}} [[lower bound]] for comparison sorting will not apply.<ref name="clrs"/> [[Bucket sort]] may be used in lieu of counting sort, and entails a similar time analysis. However, compared to counting sort, bucket sort requires [[linked list]]s, [[dynamic array]]s, or a large amount of pre-allocated memory to hold the sets of items within each bucket, whereas counting sort stores a single number (the count of items) per bucket.<ref name="knuth"/>