4 ms·
where is quicksort?
by ramki 16y ago
where is quicksort?
- jacquesm 16y agoToo fast to hear. But nice to look at: http://www.youtube.com/watch?v=vxENKlcs2Tw&feature=related http://www.youtube.com/watch?v=vxENKlcs2Tw&feature=relat...
- sesqu 16y agoBullshit on the too fast. Mergesort never needs more comparisons than quicksort, and mergesort was featured.
- jacquesm 16y agoErrm. Yes. I know that. It was a joke...
- sesqu 16y agoI've noticed that we don't share the same sense of humour. Generally speaking, I've seen too many people assert that quicksort is blazingly fast to believe all of them were joking. It doesn't particularly help that the major sorting algorithms are severely fragmented, because people optimize variously for stability, time, space, comparisons, swaps, cache locality, parallelizability, best case, worst case, average case, amortized average case, arrays, lists, integers, objects...
- jacquesm 16y agoquicksort has very bad performance on the wrong data. But on the kind of data that the test showed it would perform more or less on par with merge sort. To suggest that quick sort would be that much faster than merge sort that you couldn't hear it when there are obviously quite a few steps is to me more than enough reason to assume a joke rather than a serious answer. Anyway, humour is a hard thing to get across online, I should have added a ;) at a minimum apologies for that, also HN seems to frown on humor (even though every now and then there are some really good jokes here http://news.ycombinator.com/item?id=1597571 http://news.ycombinator.com/item?id=1597571 ) this one was reasonably lame but the subject wasn't all that serious to begin with. Sorting is enough of an issue that Knuth devoted the better part of a very thick book to it and to this day there are plenty of people that think that 'one size fits all'. The more you know about your data the faster you can sort it.
- jemfinch 16y agoMerge sort may use an optimal number of comparisons, but that doesn't stop it from being slower than quicksort in most cases in real life.