On Sunday, 17 November 2013 at 03:14:41 UTC, Xinok wrote:
On Sunday, 17 November 2013 at 02:44:45 UTC, Vladimir Panteleev
wrote:
On Saturday, 16 November 2013 at 22:11:46 UTC, Xinok wrote:
And the results (last number is predicate calls):
Current Unstable Sort 50ms 32783474
New Unstable Sort 69ms 21503542
Timsort 35ms 3905887
For the record, I tried both SwapStragegy options with my data
(the data that got me to start this thread), and although
TimSort did fewer comparisons (predicate calls), it ran about
20% slower.
Could you try running a benchmark on the same data using this
instead?
https://github.com/Xinok/XSort/blob/master/unstablesort.d
My implementation of quick sort has some odd tweaks which makes
it slower in some cases, but I've never invoked worst-case
behavior by accident.
Sorry for the late reply - my access to my home PC was spotty in
the past week.
I wasn't entirely correct in the parent post - I didn't test
things in the same way as the original problem, since I
originally encountered it while using multiSort. multiSort can't
use stable sort, because "stable $(D partition3) has not been
implemented yet". If I hack multiSort to use TimSort instead of
QuickSort, the program finishes quickly.
I reran the test in the same way as in the parent post, incl.
with unstableSort. Here are the results:
SwapStrategy.unstable: 560576749 comparisons, 4796076 ticks
SwapStrategy.stable : 340617464 comparisons, 5757974 ticks
unstableSort : 573916901 comparisons, 5255061 ticks
