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...
