Re: Mergesort algorithm for linked lists

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

True. But seeing how mergesort is one of the only N * log N sorts that can
be stable, it is desireable to preserve stability even if reversed. And that
means special treatment for equal elements. It can be done.

And note there is still a worse case: An alternating zig-zag pattern that
ascends and descends.
By worse case I mean it is still N * log N, but the sort will have the most
amount of work to do and the greatest amount of auxilary space will be
consumed.

Stephen Howe



.

Relevant Pages

  • Re: reversing a byte
    ... to reverse a byte. ... amount of time any operation requires, ... of space any executable code occupies, ... consumption of the computer running the code, ...
    (comp.lang.c)
  • Re: SPOILER: Independent 26/05/08 (was Re: SCWC 52 Results)
    ... *not* a definition and no amount of saying it loud will make it one. ... As I understand it the debate is whether the clue ... cryptic crossword purposes. ... the reverse of a definition - DIAL + a reversal indicator in the clue where ...
    (rec.puzzles.crosswords)
  • Re: Sort registers
    ... To get part of an indexed key to be desceding you reverse the value. ... If for example the value of B will be between zero and 9 then subtract ... I do this where I want an alternate key in descending date order. ...
    (comp.lang.cobol)
  • RE: Deriving Exactly XXX Amount of Weekdays
    ... (in reverse) ... Luke M ... "Rob" wrote: ... Either of the cells can hold any date and any amount ...
    (microsoft.public.excel.worksheet.functions)
  • Re: DOCUMENT ORDER; DOCUMENT PRINTING
    ... > My Word 2003 Open box lists the documents in reverse alphabetic order ... switches between ascending and descending sort order. ... you may have reverse printing selected in the ... printer driver, which is separate from Word's setting. ...
    (microsoft.public.word.docmanagement)