If you are sorting nonnegative numbers and you know the maximum possible number M, then you can do as follows. Declare an array output of M elements, fill it with zeroes, go through a given array input and for each number k in input, assign 1 to the kth element of output. After that, go through output in 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 of input is 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).