O(n) sorting array by value - get indexes I am in search of a linear-time sorting algorithm that is capable of returning an array B of indices A, sorted on the value of the corresponding element of A.

For example:


Input = [2, 6, 8, 9, 1, 7, 0]
Output = [6, 4, 0, 1, 5, 2, 3]


Things I have tried:

Storing the index and value in one number, using something like this:

long number = value &lt;&lt; 16 | index;


And then applying Countingsort. This however did not work since the JVM couldn't handle an array of ~ 2 million elements. (= the highest "number" value).

The logical solution to that problem was put everything in a map, but I was unsure whether it would still be linear..
Every problem can be solved with yet another indirection:

First create B as an array of self-indexes - i.e set B[i] = i for all i.  Next create a 'comparator' object around A, which compares integers i and j by actually comparing A[i] with A[j].  Now sort B using this comparator.