Suppose you have 100 thousand integers ranging from 1 to 1 million . How will you sort the integers in linear time?
Since the range of the input array is given we can apply counting sort algorithm to sort the array. The algorithm works as :
Time complexity = \( O(n) \). public int[] countingSort(int[] input, int range) { |