A comparison operation for lists, based on P(a > b)
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.