Worst-case performance of quickSort / getPivot

[Xinok]

On Friday, 15 November 2013 at 21:46:26 UTC, Vladimir Panteleev 
wrote:
> ...

I'm a horrible procrastinator, I should have had this fixed over 
a year ago, lol. Anyways, I posted a bug report about this 
problem long ago and a working solution has been gathering dust 
waiting to be implemented in Phobos.

Bug report (poorly titled):
http://d.puremagic.com/issues/show_bug.cgi?id=7767

Solution:
https://github.com/Xinok/XSort/blob/master/unstablesort.d

* It's an introsort which falls back to a bottom-up binary heap 
sort after so many recursions to guarantee O(n log n) performance 
in the worst-case.

* It chooses the pivot from a median-of-five. It adds nearly zero 
overhead and results in a noticeable decrease in comparisons 
(predicate calls). I see no reason why not to add this.

* My solution uses a binary insertion sort for sublists up to 32 
elements long. This reduces comparisons as well but also adds a 
fair amount of overhead. It's about 15-20% slower when sorting an 
array of integers. My idea is to use this by default and 
specialize the linear insertion sort when the element type and 
predicate are known.

* Regardless of these improvements, I think Timsort should be the 
default sorting algorithm. It's the better choice in many (most?) 
cases and, well, it's stable. Quick sort would still be available 
for those cases in which it's faster and stable sorting isn't 
needed.


Well, it's Saturday and I have no plans. Let's see if I can't get 
a pull request done by the end of the day...