Possible improvement to std::list::sort

[David Kastrup]

Ivo Doko <ivo.doko@gmail.com> writes:

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

Not really.  You do the mergesort on the forward list, then reconstruct
the backward list at the end (there is no point in doing backward list
maintenance for O(n lg n) operations when you can do it O(n) at the
end).  There is no pre-merge pass necessary for getting the next
iterator since the next iterator happens to falls out as one result of
sorting the first half.

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

I strongly suggest that you pick up the mergesort code I posted to the
list.  It gets along fine without pre-merge pass.  It does not even do
explicit recursion.

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

So?  n*m*((1/(n+1))+(1/(m+1))) _is_ O(n+m).  Do the math.  You can also
write it as

          m       n
m + n - ----- - -----
        n + 1   m + 1

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

With all due respect, I know the math.  IÂ derived the numbers for
Mergesort before I even heard of the master theorem.  And it's not like
you cannot look them up in Volume 3 of "The Art of Computer Programming"
anyway.

Check out my implementation and then tell me again that I do not know
what I am talking about.

You can find it at
<URL:https://gcc.gnu.org/ml/libstdc++/2013-07/msg00010.html>

-- 
David Kastrup