Re: Mergesort algorithm for linked lists

Eventually, I came up with my own implementation (see below) which seems
to perform quite well. The algorithm is my own idea - at least I don't know
if anybody else has come up with this before.

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)

====

It is known. This is natural mergesort. Robert Sedgewick talked about it in
one of his books.
You can't do a natural mergesort for arrays but it is dead simple for linked
lists.
You exploit any pre-existing order anywhere. I would be exceptionally
exceptionally surprised if it is not discussed in Kuth's 3rd volume
somewhere.

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.

Stephen Howe



.

Relevant Pages

  • Re: Mergesort algorithm for linked lists
    ... one of his books. ... You can't do a natural mergesort for arrays but it is dead simple for linked ... This would be to guard against the reverse order distribution to start with. ...
    (comp.lang.c)
  • Re: Mergesort algorithm for linked lists
    ... one of his books. ... You can't do a natural mergesort for arrays but it is dead simple for linked ... This would be to guard against the reverse order distribution to start with. ...
    (comp.lang.c)
  • Reducing Matrix
    ... Whoops, the algorithm I really meant was: ... You need to sort delete_rows (reverse order) or - better still - use Jos's simultaneous removal. ...
    (comp.soft-sys.matlab)