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.
- 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 << 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..