Re: Mergesort algorithm for linked lists

"Stephen Howe" <sjhoweATdialDOTpipexDOTcom> wrote:
I am not sure why the OP had followup's set to comp.lang.c (where it
seems off-topic to me) and not comp.programming (on-topic). I did not
notice the followups.
This is a re-post to comp.programming (SJH)

Yes, you are right that this is a bit off-topic in comp.lang.c and
belongs to comp.programming. But surprisingly I got a lot of helpful
posts in comp.lang.c during the last two weeks compared to two posts in
comp.programming. So it's "tempting" to post this there because the
audience seems to be larger. Moreover, the whole thing is also a bit
about how to do this effectively in C, so c.l.c is not to wrong either.

You exploit any pre-existing order anywhere. I would be exceptionally
exceptionally surprised if it is not discussed in Kuth's 3rd volume
somewhere.

Yes, somebody pointed this out in the clc thread. I have just ordered
Knuths books. Yes, it's shameful I don't have them already, but I have
Sedgewick, one from Wirth etc. and as a last excuse I am not a computer
scientist by education.

Best of all, the sort will be O(N) if it is already sorted and it does
well on data that has partial orders.
The worst case for natural mergesort is if the data is in reverse
order to start with. There are no "runs" then.
I would be tempted to do a hybrid where all runs were at least 4
elements no matter what.
This would be to guard against the reverse order distribution to start
with.

Sounds interesting. I'll try this. I did some tests already with
insertion sort for small runs, but it became faster. In the clc thread
somebody elaborated why this is the case.

.