Re: Mergesort algorithm for linked lists

pete wrote:
Googmeister wrote:
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 am unfamiliar with "*natural* mergesort".

There has been a long discussion on comp.lang.c. This thread is a
late offshoot.


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.)

If the occurance of pre-sorted lists is likely, you can do a
preliminary scan to decide if the list is sorted, reverse-sorted,
or unsorted. If sorted, nothing to do. If reverse sorted list
reversal is O(n). Otherwise you can accept the O(NlogN) of
mergesort. At most the preliminary test has added to the constant
factor. Your data will govern whether or not it is worthwhile.
Note that you can abandon the preliminary scan early once lack of
any sorting is detected.

--
Chuck F (cbfalconer at maineline dot net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.net>

.

Relevant Pages

  • 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)
  • 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)
  • Re: What about an EXPLICIT naming scheme for built-ins?
    ... * I believe that the current naming and reversed) is not ... * Naming the current builtins sorted() and ireversedwould make ... -- sortedand reversedshould work similarly, returning lists. ... returning an iterator for the reverse list is the ...
    (comp.lang.python)
  • Re: reverse not working: CL-USER> (rvrs (1 2 3)) (((NIL . 3) . 2) . 1)
    ... So my reverse gets the spirit right but doesnt deliver exactly what I ... All lists have them, but they are almost always not shown to ... What the dot tells you, when you see it appear, is that none of the ... The really inelegant part is the call to APPEND. ...
    (comp.lang.lisp)
  • Re: Merging sorted lists/iterators/generators into one stream of values...
    ... > trick with reverse to reduce memory copying, ... > Wonder if bisect can deal with reverse-sorted elements. ... and if it can't deal with reverse-sorted lists it would ... You'll also need to check for StopIteration ...
    (comp.lang.python)