Re: Mergesort algorithm for linked lists

CBFalconer wrote:
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.

As it turns out, the natural mergesort excels on a sorted list and in
general takes advantage on any preorder in the list. But even the
non-natural mergesort does well on sorted as well as reverse-sorted
lists.

The reason is given above by Googmeister: The merging stops comparisons
if one list is exhausted - the other one is simply appended.

So I believe that looking for natural runs is enough of an optimization.
Adding preliminary scans for various "pathological" cases is rather
useless for the general case.

.

Relevant Pages

  • 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)
  • 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: Newbi Q: Recursively reverse lists but NOT strings?
    ... Python strings are not lists! ... different functions: one to reverse a list and one to reverse a string: ... I couldn't find in the Python docs what this form of slicing means: ... It works for creating a reversed copy of either a string or a list, ...
    (comp.lang.python)