Re: Mergesort algorithm for linked lists

The worst case for natural mergesort is
if the data is in reverse order to
start with. There are no "runs" then.

That's completely wrong for stable mergesorting of linked lists
and mostly wrong for stable mergesorting of arrays.

I was talking about *natural mergesort* not vanilla or ordinary mergesort.

I ought to make it clear that by worse case of natural mergesort, it is
still O(N * log N), it is just that natural mergesort does the most amount
of work in this case and the amount of auxilary memory is maximal.

Stephen Howe


.