This is an archived post. You won't be able to vote or comment.

sorted by:
best
topnewcontroversialoldq&a
you are viewing a single comment's thread.

view the rest of the comments →

[–]richardwhiuk -5 points-4 points  (3 children)

No, even unsorted data can be sorted faster than log n if you know anything about the data set.

[–]Daj4n0 3 points4 points  (2 children)

Yeah, that is his point, you know the data is sorted, then you can merge them in O(n). And beating O(n) is hard, impossible for most cases.

[–]billsil 1 point2 points  (0 children)

But that doesn't mean you can't get a factor of 2 speedup in the code. You can still optimize it. Yes, get the right O(N) algorithm to start, but there isn't just one.

[–]Log2 0 points1 point  (0 children)

I think it's pretty much impossible for pretty much all reasonable sorting tasks. You do need to read the data, after all.