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