<i>counting the number of inversions of a sequence in O(n \lg n) time</i><p>Counting inversions is equivalent to sorting. That's why it's 0(n log n). Any sorting algorithm can become an inversion counting algorithm by incrementing a counter instead of rearranging the input values. Inversions are the first topic in <i>The Art of Computer Programming</i> Chapter 5. Very much worth reading if you dig this stuff.