Counting Inversions via Rank Queries

byorgey.wordpress.com

11 points·johndcook··3 comments

counting the number of inversions of a sequence in O(n \lg n) time

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 The Art of Computer Programming Chapter 5. Very much worth reading if you dig this stuff.

Does this apply to integer keys in the computational models that can do operations other than simple comparisons? In the transdichotomous model, I thought the best known sorting algorithms were O(n lg lg n) worst case, while the best known inversion counting models were Ω(n √ lg n), following “Counting Inversions, Offline Orthogonal Range Counting, and Related Problems”.

Thanks. I didn't think about it. I was only thinking of the general case of sorting.

Integer sorting seems like a case where there's meaningful metadata (maximum integer) and the algorithm is written only for that case (and assumes suitable hardware). These aren't radical assumptions and the optimization may have a lot of practical applications. But once I get to specify the inputs, then O(1) sorting is trivial. Specify the input as sorted lists. To me, it only seems a matter of degree. But admittedly, what can be represented as an integer is a much more reasonable degree of specification.

Reply on news.ycombinator.com