Re: Mergesort algorithm for linked lists

Stephen Howe wrote:

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.

Mergesorting a reverse ordered list requires the minimum
number of comparisons for a given number of elements;
that is the same number of comparisons
required for stable mergesorting of
an already sorted list of same size.
That is to say that the work involved in a
stable mergesorting of a reverse ordered linked list,
is the same as the amount of work involved
in a stable mergesorting of a foward ordered linked list

For a stable mergesorting of an array,
the reverse ordered array
requires the minimum number of comparisons
but the maximum amount of data movement,
which is not the same as a worst case.

--
pete
.