Possible improvement to std::list::sort
Ivo Doko
ivo.doko@gmail.com
Wed Oct 8 17:57:00 GMT 2014
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.
More information about the Libstdc++
mailing list