O(n) sorting array by value - get indexes

Question

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

Answer 1

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.

Answer 2

You included radix sort as a tag. Assuming you write your own radix sort program, it could first sort an array of indices I[] according to values in A[]. For your example for A, the result would be:

A[] = {2, 6, 8, 9, 1, 7, 0}
I[] = {2, 3, 5, 6, 1, 4, 0}

In your example, B[] is the rank of A. To convert the sorted indices into a rank use something like:

for(i = 0; i < n; i++)
    B[I[i]] = i;

which will result in:

B[] = {6, 4, 0, 1, 5, 2, 3}

The entire process would be linear in time.

Answer 3

Assuming you can sort the elements in A in linear time (e.g. they're smallish integers), you can produce an array of indices by sorting tuples of $(a,i)$ where $a$ in an element from A and $i$ is its index

index_sort(A):
    B = []
    for i in 0 to length(A):
        append (A[i],i) to B
    sort B in linear time, considering only the first component of the tuples for the ordering
    C = []
    for i in 0 to length(A):
        let (a,j) = B[i]
        append j to C
    return C