AmatuerGeek

  Counting Sort Algorithm Sorting Algorithm Quick reference Complexity Worst case time O(n) O ( n ) Best case time O(n) O ( n ) Average case time O(n) O ( n ) Space O(n) O ( n ) Strengths: Linear time . Counting sort runs in  O(n) O ( n )  time, making it asymptotically faster than comparison-based sorting algorithms like  quicksort  or  merge sort . Weaknesses: Restricted inputs . Counting sort only works when the range of potential items in the input is known ahead of time. Space cost . If the range of potential values is big, then counting sort requires a lot of space (perhaps more than  O(n) O ( n ) ). The High-Level Idea Counting sort works by iterating through the input, counting the number of times each item occurs, and using those counts to compute an item's index in the final, sorted  array . Counting How Many Times Each Item Occurs Say we have this  array : And  say we know all the numbers in our  array  will be  whole numbers   ↴   between 0 and 10 (inclusive). The idea