Did you mean O(n)? It seems hard to sort n items without at least touching all of them once, which would make the time complexity linear (O(n)) instead of constant (O(1)). Or are you talking about storage needs? Then it sounds very hard to go sub-linear ... I'm confused.

I'm certainly not a good theoretical computer scientist, but I did quickly google this and I couldn't find any trace of constant-time sorting (unless you goalpost it to have O(n log n) processors, but that is kind of cheating, here).