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

[David Kastrup <dak at gnu dot org>]

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

> On 2014-10-08 21:06, David Kastrup wrote:
>> 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.
>
> Oh, indeed. No way to do that without access to the internal pointers
> of the list nodes, though.

The code I linked to uses iterators.

>> 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
>
> Ah, you are correct.
>
> That was a silly oversight on my part - I completely overlooked the
> (1/(n+1) + 1/(m+1))
> part of the product.
>
> Even so, there's a problem. Let's say m = n = k. Then
>
> m + n - m/(n+1) - n/(m+1)
> = 2k - 2k/(k+1)
>
> whereas if m = 1, n = 2k-1
>
> m + n - m/(n+1) - n/(m+1)
> = 2k - 1/(2k) - (2k-1)/2
>
> As can be seen here:
> https://i.imgur.com/TgrQFbB.png
> the former grows faster than the latter. So, according to this
> formula, it is still more efficient to merge unbalanced than balanced
> lists.
>
> Something is definitely wrong there.

That's the count for a single merge pass.  With equal sizes, the problem
is reduced by a factor of 2.  With 1 vs. 2k-1, the problem is reduced by
a single element.

Let's assume that we are sorting 2^k elements.  When taking the complete
sort, the even subdivision takes in the _worst_ case (which is about n
larger than the average case but easier to analyze) 2^k*(k-1)+1
comparisons.  With n=2^k, this is n*(-1+lg n)+1, O(n lg n).

Now compare this to the _average_ case when merging a single element
with k other elements.  That takes on average
1 + k/2 - 1/(k+1) comparisons.  Repeating this for k from 0 to n-1 gives

n^2 + 3n
-------- - H_n
   4

comparisons where H_n is 1/1+1/2+...1/n and close to ln(n).  So
basically O((n^2)/4).

The better the merged lists are matched in size, the larger the scale
reduction of the problem.

> Regardless, I doubt any of this is within the scope of this mailing list.

Shrug.  If we are assuming that neither of our code will end up in
libstdc++, and that looks like a reasonable assumption to make, it's
probably not within the scope of this mailing list.

-- 
David Kastrup