Computer sorts require at least linear time, as you need to read the input (if you don't know other things about the input, say it has an uniform distribution).

Computer sorts require at least linear time, as you need to read the input (if you don't know other things about the input, say it has an uniform distribution). There are several linear time sorts, sleepsort, postman sort, counting sort. (For a bounded set of numbers or sortable keys.) But there is an (almost) truly constant time sort, using an abacus instead of a computer: https://en.wikipedia.org/wiki/Bead_sort https://en.wikipedia.org/wiki/Bead_sort