Possible improvement to std::list::sort

[Ivo Doko]

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.

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

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

I never said you didn't know what you were talking about. But, everyone 
makes mistakes. Just like I did in my previous e-mail.


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


--
Ivo Doko