[jbapple]

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”.

[brudgers]

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.