Which non-comparison sorting algorithm runs in O(n + k) time for n integers in the range 0 to k?
Show answer
Counting sort
Counting sort works by counting the occurrences of each unique value and using those counts to determine the position of each element in the output. It is stable and efficient when the range of input values is not significantly larger than the number of items.
Also asked as:
- Which non-comparison sort is efficient when the range of input values (k) is not significantly larger than the number of items (n), resulting in O(n + k) time?