Re: Possible improvement to std::list::sort

[Ivo Doko <ivo dot doko at gmail dot com>]

On 2014-10-08 08:36, David Kastrup wrote:
> Natural merge sort rather than base-2.  The problem with that is that it
> either leads to worse divisions in the divide-and-conquer (if you make
> use of the discovered natural runs) or that you waste comparisons on
> each pass (if you don't make use of the discovered natural runs).
> Either affects the worst-case behavior, and merge sort degrades into
> worst case behavior very easily (which is actually a feature since its
> worst case is pretty good):
>
> Merging two sorted unrelated lists of size n and m takes an average of
>
>        1       1
> n m (----- + -----)
>      n + 1   m + 1
>
> comparisons if memory serves me right.  So for n and m about equal,
> that's less than 1 away from the worst case of n+m-1.
>
> So since we are almost always talking about worst case behavior in the
> mergesort case, one does not want to make it even "slightly worse".
>
> That's different from quicksort where the worst case is much more of a
> statistic anomaly.  There it pays off to make sure that degenerate input
> does not trigger the worst case.
>
> But with merge sort, you have the worst case behavior all the time, so
> you don't want to make it even somewhat worse.

I understand what you're saying, however, in order to perform mergesort 
on a (doubly) linked list without performing unnecessary in-loop 
iteration, one first has to make a pre-merge pass through the list to 
store the region boundaries (iterators) in another list anyway, which is 
then iterated through in the loop and the region boundaries passed to 
inplace_merge, reducing the number of region boundaries by about a half 
upon each step of the loop.

With this, having the pre-merge pass also detect and group pre-existing 
ascending and descending runs makes almost no impact on the speed of 
that pass, but it speeds up the merge operation afterwards - yes, even 
though the region sizes may not be equal then.

There is something wrong with your formula up there - merging two sorted 
lists takes time proportional to the sum of their lengths, not the product.
I mean, if it were product, then sorting as unbalanced lists as possible 
would be better, since the function
f_n(x) = (n-x)(n+x) = n^2 - x^2
clearly has the global maximum in x=0, ânââ.

With that, establishing bigger sorted regions for the mergesort pass is 
better since it reduces the number of merge loop steps.