3 ms·

Okay, this is a bit of a side issue, but a few details about the NumPy Quicksort are bothering me. First, we've known since 1997 how to improve Quicksort's wor

Okay, this is a bit of a side issue, but a few details about the NumPy Quicksort are bothering me. First, we've known since 1997 how to improve Quicksort's worst case number of comparisons to O(n log n) for an n-item list. (Track the recursion depth and switch to Heap Sort on the current sublist if the depth exceeds 2 log_2(n); this is usually called "Introsort".) This optimization is pretty well known. For a front-line library like NumPy to include a quadratic-worst-case sorting algorithm in 2014 is ridiculous. Second (and rather less important), we can't write Quicksort with constant extra space usage, since, when sorting a small sublist, we need to remember the pivots in the larger sublists we are in the middle of sorting. So Quicksort's extra space usage is going to be at best O(log n) subscripts/pointers for an n-item list. However, the docs say 0 work space required. This would be correct if the sort were written in "C" and NumPy only counts Python objects in its space usage, but I can't find anywhere this is stated. Third (and perhaps very important), I don't see anything in the docs about locality of reference or any other is-this-algorithm-friendly-to-modern-processor-architectures issues. There are good reasons Quicksort is largely being abandoned for standard-library sort implementations.

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 ago
  Well, 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.)

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 ago
Well, 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.)