Re: Mergesort algorithm for linked lists

On Jan 29, 3:24 pm, "Stephen Howe" <sjhoweATdialDOTpipexDOTcom> wrote:
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.

Of course, it is a trivial modification to search for partitions that
are either ascending or descending, and tag them as such.
With this simple variant, the reverse ordered set is also fully sorted
after n operations (we just peel the data from the far end instead of
the near end when accessing a reversed partition).

.