# A comparison operation for lists, based on P(a > b)

Consider two lists $A$ and $B$, both containing $n$ numbers. A comparison operation can be defined based on the probability of uniformly selecting an element $a$ from list $A$ and an element $b$ from list $B$ such that $a>b$.

More precisely, define $$Q(A,B) = \sum_{i,j} \text{sign}(a_i-b_j)$$ If $Q(A,B) = 0$, then we can say the lists "tie". If $Q(A,B)>0$ then $A$ "beats" $B$, and likewise $Q(A,B)<0$ can be said as $A$ "loses" to $B$.

The naive way of calculating this comparison of lists involves checking each pair of elements and thus takes $n^2$ time.

Is there a faster way to calculate this?

Note, that somewhat non-intuitively, $A$ can still beat $B$ even if the average value of $A$ is less than $B$. (Also, even more non-intuitive, this comparison operator is non-transitive. Known as "intransitive dice", you can have dice such that A beats B, B beats C, C beats A.)

I believe if we take the $O(n \log n)$ hit to sort $A$ and $B$ first, then there should be a better way to calculate the comparison. But I'm having trouble filling in the pieces. Hopefully this is a useful hint instead of a red-herring.

Let $A \cup B$ denote the union of $A$ and $B$. Sort $A \cup B$ into increasing order, keeping track for each element which list it came from. Now for each element of this sorted list, annotate it with the number of elements of $A$ that are smaller than it and the number of elements of $B$ that are smaller than it. Those annotations can be filled in with a single linear scan (starting from the start of the list, and scanning left-to-right, and keeping track of the number of elements of $A$ and $B$ seen so far). Then you can compute the sum from those annotations: for each $i$, you can compute $\sum_j \text{sign}(a_i-b_j)$ directly from the annotation.
This algorithm takes $O(n \log n)$ time: $O(n \log n)$ time to sort, plus $O(n)$ for the scan, plus $O(n)$ time to add up the sums.