5 ms·
any sort that only uses comparisons is provably not better than n log n. Hence whatever Thorup is, it doesn't work for arbitrary input, and must assume somethin
by xdavidliu 3y ago
any sort that only uses comparisons is provably not better than n log n. Hence whatever Thorup is, it doesn't work for arbitrary input, and must assume something further, something like "all elements under 1000 or something"
- utopcell 3y agoI think the parent's argument is that, since they only evaluated their algorithms on sorting arrays of 32-bit or 64-bit integers, it is fair game to compare against integer sorting algorithms for which we have better complexities than O(nlgn).
- reaperman 3y agoThis seems like a very valid point for iopq's clarifying point in the context of what still might exist to be discovered in the set of theoretically possible new algorithms, though doesn't change that dheera set the bar much, much higher than most people would agree with. Thank you.
- xdavidliu 3y agobut the number of elements in the array is also a 32 or 64 bit integer, so you still cannot do better than O(n log n) even with fancy radix sort or whatever
- utopcell 3y agonot with radix sort, but you can do better when your elements are integers, even if there there are a lot of them, i.e. even when n ~ 2^32.
- xdavidliu 3y agointeresting; got an example or link? What exact asymptotic form do you mean by "better" here?
- utopcell 3y agoThere are many such algorithms. For example, [1] is expected linear time, deterministic O(nlglgn) time and linear space. Note that the proposed ML (micro-)algorithms rely heavily on the fact that they are sorting 32-bit or 64-bit integers because they are using conditional moves. A conditional move avoids a branch by converting the instruction to a no-op when the condition doesn't hold. This is fine when moving 4 or 8 bytes because it can be done in a single clock cycle, but you can't apply the same technique when sorting larger objects. [1] https://dl.acm.org/doi/pdf/10.1145/225058.225173 https://dl.acm.org/doi/pdf/10.1145/225058.225173
- graycat 3y agoThe Gleason bound is n log(n) and says that no sorting algorithm based on comparing pairs of keys can be faster. Heap sort meets the Gleason bound so is the fastest possible in this context. Actually the usual versions of quick sort are slower. If the keys are not too long, radix sort is O(n) and faster. All this has been well known for decades. I explained a little more in another post in this thread.
- CyberDildonics 3y agoI think you are getting your information mixed up. Here is a comparison that shows quicksort running in 1/10th the time as heapsort. https://johnysswlab.com/why-is-quicksort-faster-than-heapsort-and-how-to-make-them-faster/ https://johnysswlab.com/why-is-quicksort-faster-than-heapsor...
- xdavidliu 3y agowe're talking about asymptotics (i.e. the exponent). Things like "1/10 the time" are utterly meaningless here.
- CyberDildonics 3y agoWho is talking about that? They said 'faster' not less algorithmic complexity. 1/10th the time is much faster.
- graycat 3y ago> 1/10th the time is much faster. No, absolutely no, it's not in any meaningful or useful sense "faster" as in which algorithm is "faster". You utterly fail to get this point.
- CyberDildonics 3y agoIf something runs in less time, it's faster. If something runs in 1/10th the time as something else it is multiple orders of magnitude faster. I don't think I've ever seen someone try to redefine 'faster' before. You keep trying to equate naive algorithmic complexity and speed, but you haven't even linked anything that shows heapsort is better than other sorts like quicksort at that. You haven't actually linked anything to back up any of what you're saying, even the irrelevant offtopic claims.