Take the 2-minute tour ×

Suppose that you're given an array A of n distinct elements drawn from some totally-ordered set. For example, you might be given

137 13 7 42 38

The goal is to produce for this array of elements a matching array B such that B[i] is the number of elements in the original array that are smaller than A[i]. For example, in the above array, we'd want to produce

A = 137  13   7  42  38
B =   4   1   0   3   2

Since 137 is bigger than four other elements (13, 7, 42, 38), 13 is only bigger than one of the elements (7), 7 is bigger than no other elements, etc.

In the most general case, where the elements in the array are arbitrary objects that can only be compared, any solution to this problem must run in Ω(n lg n) in the worst case because once we have this table, we can sort the array in O(n) time by making a new array of n elements, then putting each element in the position specified in the table. However, what I don't know is how fast we can construct this table when the elements are not arbitrary values.

My question is this: suppose that you're given an array of n distinct integer values and want to construct a table of order statistics for that array. What is the most efficient algorithm for doing so? If it helps, you can assume the integers are positive and that the largest of them has value U.

Currently, the best I have is an O(n lg n) solution that works by making a copy of the array, sort it, then for each integer in the original array, doing a binary search to find its position in the new array. This is a fine solution, but I was really hoping that there would be some better way of doing this.

Thanks for any thoughts/ideas/solutions you might have!

And no, this isn't homework. :-)

share|improve this question
Not a complete answer, but you can use en.wikipedia.org/wiki/Radix_sort which is O(kN) for integers. –  eulerfx Mar 17 '11 at 20:32
@eulerfx- IIRC radix sort runs in O(n lg U), where U is the largest integer you're sorting. I believe that if you use a van Emde Boas tree you can actually drop this down to O(n lg lg U), though the constant factor is probably a lot higher. –  templatetypedef Mar 17 '11 at 20:51

5 Answers 5

up vote 6 down vote accepted

Step 1: sort the original array indexes.

A  = 137  13   7  42  38
I  =   0   1   2   3   4

A' =   7  13  38  42 137
I' =   2   1   4   3   0

Step 2: for every I'[i] = j assign B[j] = i.

I' =   2   1   4   3   0
i  =   0   1   2   3   4

B  =   4   1   0   3   2
share|improve this answer
+1 This is a great solution. I didn't think of keeping the original indices around. –  templatetypedef Mar 17 '11 at 20:40
you beat me to it. –  AShelly Mar 17 '11 at 20:42
Curiously step 2 is exactly the same index sort operation as step 1, but can be done in O(n) as a pigeonhole sort. –  aaz Mar 17 '11 at 20:52

There is at least no comparison-based approach to this problem that does better than O(n log n), which is a general lower bound for comparison-based sorting. (Otherwise you could apply the new magical procedure and afterwards iterate over B to construct a sorted version of A).

If the integers of your input array A however are restricted to some known range, say [1..M], then you can do better - i.e. O(M + n) - by marking those numbers (in an array, say L[1..M]), which occur in A, remember their position in A and afterwards to a sweep through L from index 1..M to construct B.

share|improve this answer
This is true, but that's an exponential-time algorithm (since M is represented in log M bits in the input). I was hoping for something polynomial in the size of the input. –  templatetypedef Mar 17 '11 at 20:37
Of course it only helps if M = o(n log n). Otherwise sorting does the trick. –  dcn Mar 17 '11 at 20:41

This doesn't improve the big-O, but your algorithm does 2 different N-LogN operations. Instead of sorting the array itself, sort an array of {value, originalIndex} structures.

Then walk through the sorted array doing rank[sorted[i].originalIndex]=i;

This is only 1 N-LogN operation.

And with a max bound on U, you could do a radix sort to get O(kN) instead (assuming you have the memory)

share|improve this answer

Most likely you want to make all combinations of the first array with n^2-n and then compare each element with the other to find the 1st number and repeat this with every number of the 1st array using a 2nd array to count.

share|improve this answer
This will work, but it's O(n^2) and I already have a general approach that works in O(n lg n) even if the inputs aren't integers. –  templatetypedef Mar 17 '11 at 20:37
Please stop begging for upvotes. If your answer deserves an upvote, you'll get it. Asking for them is just noise, and looks really bad. –  Ken White Apr 1 '11 at 2:41
@Ken: Can you explain me why it looks bad? Aren't you use to beg? Where I came from I beg a lot!!! –  Phpdna Apr 1 '11 at 3:12

A way to do it is using prefix sums

share|improve this answer
@fabrizioM- This link appears to be broken; can you post a different link? –  templatetypedef Mar 17 '11 at 21:07
Fixed link, checkout the postscript file. –  fabrizioM Mar 17 '11 at 21:24
Also that way is higly parallelizable and is how GPU solutions work –  fabrizioM Mar 17 '11 at 21:26
I just started looking over this paper and WOW does this look like a cool tool. I just found what I'm going to spend my afternoon doing. :-) –  templatetypedef Mar 17 '11 at 21:29
Oh yes definitely worth looking and playing with it –  fabrizioM Mar 17 '11 at 21:31

Your Answer


