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 1 Credited ToHarold H. Seward (1954) 1 Connections
Sources
1. 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.
View the SourceReader 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.