Re: Mergesort algorithm for linked lists

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

I am unfamiliar with "*natural* mergesort".

Natural mergesort is where you take advantage of any builtin order of the
list.
Effectively you split the list into a series of runs as presented in the
initial data.
So if it is already sorted, then the "*natural* mergesort" will generate 1
run of N elements, therefore it is O(N)

But if it in reverse-order, any comparison is such that each element will be
in its own run of length 1.
It is still O(N * log N) to sort as you merge adjacent runs - but you will
do the maximum amount of merging.

Stephen Howe


.