On 11/16/13 2:11 PM, Xinok wrote:
On Saturday, 16 November 2013 at 20:35:21 UTC, Andrei Alexandrescu wrote:
On 11/16/13 11:46 AM, Xinok wrote:
* 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.
There's something fishy about a more restricted algorithm doing better
than one that's less restricted. We must improve unstable sort, not
make stable sort the default.
Andrei
Timsort is an "adaptive" sort. It's able to achieve better performance
in many cases by exploiting patterns in the data.
This is in response to what? Are you trying to talk me out of the
pigeonhole principle?
I decided to make a nice little test using my benchmark code here:
https://github.com/Xinok/XSort/blob/master/benchsort.d
I understand and appreciate that Timsort is a nicely optimized
algorithm. This has nothing to do with it doing more work than an
unstable sort that is just as nicely optimized.
At the end of the day whatever stable sorting algorithms are out there,
their set is included in the set of all sorting algorithms. In order to
preserve stability, stable sorting algorithms need to do nonnegative
extra work.
Andrei
