On 4/22/13 5:52 PM, bearophile wrote:
Andrei Alexandrescu:
c) add introspection to the algorithm, i.e. if an attempt to partition
hits the worst case or near worst case, just try another pivot instead
of moving forward with the sorting stage.
Or switch to a sort that is guaranteed to have a pseudo-linear complexity.
I am not sure, but I think the C++ STL sort does this.
There's not "the C++ STL sort". Any implementation is fine as long as it
has O(n log n) expected run time.
TimSort is slower on average.
Here it's not easy to define what "average" is. Python devs think that a
common case is an array with mostly sorted data with unsorted data at
the end.
Note that in this case it's sorted data followed by its smallest
element. (Changing the value does improve sped.) This is hitting a
corner case: median of 3 will pick the smallest element, which will lead
to an inefficient partition. I haven't looked at the code, but it seems
the smallest element again makes it to the beginning and the end of the
array so it's again picked etc.
One simple solution to this (which I forgot to mention) is picking a
pivot at random.
Andrei
