3 ms·
>>There are good reasons Quicksort is largely being abandoned for standard-library sort implementations. Maybe I am not up to date on that but there was some f
by bluecalm 12y ago
>>There are good reasons Quicksort is largely being abandoned for standard-library sort implementations.
Maybe I am not up to date on that but there was some fuss lately about implementation of dual pivot quicksort in Java standard library which was to replace the old implementation (http://www.docjar.com/html/api/java/util/DualPivotQuicksort.java.html http://www.docjar.com/html/api/java/util/DualPivotQuicksort....)
My experience is also that quicksort smokes all merge-sort hybrids on partially sorted inputs but of course that might be because my inputs had something very specific in them when I tested it.
Quicksort is very cache friendly (pivot sits in a register, and you keep comparing to what is already in cache assuming you sort small structs with key in them).
My intuition is that mergesort hybridgs being faster in some languages is very specific to implementation of those languages and they will lose once you are down to sorting C structs.
- ggchappell 12y agoWell, perhaps I'm not terribly up-to-date on the issues I mentioned third, either. FWIW, there is a comment on why GNU libc defaults to Merge Sort for qsort() on Reddit: > The reason we made qsort() default to using merge sort was, indeed, that it always makes fewer compares than quick sort. We thought that in the common case, people would sort small objects (numbers, pointers) rather than large objects, and that therefore the performance would be dominated by comparisons rather than data movement. Link to full comment: http://www.reddit.com/r/programming/comments/1jxq4/ask_reddit_why_does_the_gnu_libc_use_mergesort_to/c1k07v http://www.reddit.com/r/programming/comments/1jxq4/ask_reddi... Since you say "pivot sits in a register", you're also talking about very small data. It looks to me like the two of you disagree. (OTOH, that comment was 7 years ago.)