3 ms·
I was under the impression (could be remembering something wrong, however) that sorting algorithms had a provable (or at least strongly believed) best-case of O
by javanix 16y ago
I was under the impression (could be remembering something wrong, however) that sorting algorithms had a provable (or at least strongly believed) best-case of O(nlogn), and that we already have algorithms that meet that.
If that is correct, most improvements would probably come from hardware and software use-case tuning.
- sp332 16y agoBig-O notation is a theoretical tool, it's somewhat useful in practice but it won't necessarily tell you which of two algorithms is faster. It doesn't tell you about cache performance, memory requirements, or even if there's a large coefficient on that n * log(n) term.
- Yrlec 16y agoThat's for comparison-based sorting algorithms (i.e. sorting objects where the only information you have about them is whether one object is "bigger"/"smaller" than the other. For objects where you have more information about the object (i.e. integers) you can sort faster. My supervisor for my Master's Thesis did just that: http://www.drdobbs.com/184404062 http://www.drdobbs.com/184404062
- adataminer 16y agoyes its an engineering exercise.