A non-comparison sort that counts the number of occurrences of each distinct key and uses those counts to place elements directly into sorted position, running in linear time when the range of possible keys is not much larger than the number of elements.
Facts
Time ComplexityO(n + k), where n is the number of items and k is the key range 2 Credited ToHarold H. Seward (1954) 2 Time Complexity
Time Complexity (category) Connections
Sources
1. Counting Sort (Wikipedia)
Wikipedia infobox: time complexity linearQuote, Wikipedia infobox: time complexity linear
linear
2. Wikipedia: Counting sort
Complexity analysis
the time for the whole algorithm is the sum of the times for these steps, O(n + k).
History
counting sort, and its application to radix sorting, were both invented by Harold H. Seward in 1954.
In Group: Distribution and Integer Sorting Algorithms, Lead section
it is an integer sorting algorithm
View the SourceWikidata: Counting Sort
Wikidata Q1124964, class allow-list match (w-wdresolver-0926)View the Source Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.