Comment by CaptainNegative

> You can generally reduce the problem to a finite alphabet by taking the finite subset that actually appears in the input.

You can generally sort any array in constant time by taking that constant to be the time it takes to sort the array using bubble sort.