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

• D.W.: There is in general no linear-time sorting algorithm for arbitrary items. Are we given some guarantees on the range of possible values of elements of A? If so, use any standard sorting algorithm (just use pointers and a custom comparison operator).
• StephenG - Help Ukraine: This however did not work since the JVM couldn't handle an array of ~ 2 million elements. Sounds like you need to read these posts on memory allocation in the JVM stackoverflow.com/questions/31382531/…

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.

• D.W.: The tricky bit is how to achieve a linear-time sorting algorithm. This answer describes the standard answer for how we'd sort if we didn't have the linear-time requirement, but it doesn't take into account the requirement from the question to sort in linear time. A standard comparison-based sorting algorithm does not run in linear time. So, I'm not sure that this answers the question that was asked. That said, I'm not sure the question is answerable in its current form, without imposing some restrictions on the input.

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