From: kagel AT quasar DOT bloomberg DOT com
Date: Wed, 5 Mar 1997 16:23:09 -0500
Message-Id: <9703052123.AA17587@quasar.bloomberg.com >
To: dlydiard AT linknet DOT kitsap DOT lib DOT wa DOT us
Cc: djgpp AT delorie DOT com
Subject: Re: Merge Sort: Doubly Linked List
Reply-To: kagel AT dg1 DOT bloomberg DOT com

I have such a sort.  I developed, and published, a sort algorithm in 1985,
specifically for linked lists.  It is easily modified for either singly or
doubly linked lists.  I have C++ source for the current version which could be
made "C" callable.  The list element class/structure is defined in a separate
header and can be modified as well.
 
There are two versions of the sort.  1) Sorts an existing list.  2)
Incrementally adds elements to a list while sorting the input stream.  Due to
the nature of the algorithm and data source delays this can be faster for file
and stream sorting than collecting all of the data before sorting.
 
The second version is ideal for sorting an input stream, like a pipe or file,
and producing a sorted output.
 
The algorithm is call Unshuffle it is a distribution/merge sort and was
published in an earlier, less efficient, form in Computer Language, November
1985.  The latest version includes several optimizations including an improved
distribution algorithm and the FASTEST merge algorithm known!  It is most
efficient for sorting lists which exhibit low entropy, ie that are already
partially ordered, while performing competitively with more conventional
algorithms like quicksort and heapsort for random data.  It is low overhead
and performs a minimal number of comparisons meaning that it's advantages over
other sorts increase as the key length or complexity increase.
 
If the list to be sorted is already ordered the sort degenerates (unfortunate
word that) to a list order verify.  If the list were composed of several sorted
segments with no disorder within each it becomes a highly efficient merge.
 
If you are interested let me know.
 
Reply to: kagel AT dg1 DOT bloomberg DOT com