4 ms·
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 the
by ralfn 3y ago
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 3y agoby "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 3y agoParent 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 3y agoSorry 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