Re: Mergesort algorithm for linked lists



On Jan 27, 11:46 pm, pete <pfil...@xxxxxxxxxxxxxx> wrote:
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.

He's talking about *natural* mergesort. Natural mergesorting
a sorted linked list of n elements takes n-1 comparisons.

I don't think a reverse sorted input is the worst case for
natural mergesort, but it's proportional to n log n comparisons.
(The reason reverse-sorted is not worst-case is that when
you're merging two lists, you will stop performing comparisons
as soon as one list is exhausted.)

.

Relevant Pages

  • Re: Mergesort algorithm for linked lists
    ... and mostly wrong for stable mergesorting of arrays. ... Mergesorting a reverse ordered list requires the minimum ... merging two lists, you will stop performing comparisons as soon ...
    (comp.programming)
  • Re: Mergesort algorithm for linked lists
    ... and mostly wrong for stable mergesorting of arrays. ... Mergesorting a reverse ordered list requires the minimum ... you're merging two lists, ...
    (comp.programming)