[ralfn]

If the thing you have to sort is within a known domain you can definitely beat o(n log(n)). Just expect crazy memory usage.

And that's only not the case in theory. But nobody owns a real Turing machine with infinite tape and truly infinite numbers. It doesn't exist in reality.

You can always divide time by multiplying space with the same factor.

[xdavidliu]

by "general sort" your parent comment means "comparison sort", and the claim (which has been proved, see CLRS intro to algorithms) is that you cannot do it in better than O(n log n) comparisons.

[yunohn]

Parent said: > not going to find a general sorting algorithm

You said: > you have to sort is within a known domain you can definitely beat

Not sure why you framed your response this way?

[ralfn]

Sorry I didn't phrase my point well enough.

Every sorting on a computer existing in reality is within a limited domain.

The general sorting problem is an artificial problem for theoretical computers with infinite memory.

It's a philosophical problem not an engineer one