If you are sorting nonnegative numbers and you know the maximum possible number M, then you can do as follows. Declare an arrayoutputof M elements, fill it with zeroes, go through a given arrayinputand for each numberkininput, assign 1 to thekth element ofoutput. After that, go throughoutputin the order of increasing (or decreasing) indices and print indices where 1 is stored. The time complexity of this algorithm is O(M). If the length ofinputis n and if M <= c * n for some constant c that does not depend on n and M, then the complexity is also O(n).