Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.3 4.3bsd-beta 6/6/85; site dg_rtp.UUCP
Path: utzoo!linus!decvax!ittatc!dcdwest!sdcsvax!ncr-sd!ncrcae!ncsu!mcnc!rti-sel!dg_rtp!throopw
From: throopw@dg_rtp.UUCP (Wayne Throop)
Newsgroups: net.lang.c
Subject: Re: Sorting linked lists
Message-ID: <276@dg_rtp.UUCP>
Date: Thu, 3-Apr-86 16:22:43 EST
Article-I.D.: dg_rtp.276
Posted: Thu Apr  3 16:22:43 1986
Date-Received: Sat, 5-Apr-86 07:28:05 EST
References: <165@ablnc.UUCP> <337@umcp-cs.UUCP> <402@mips.UUCP> <423@mips.UUCP>
Lines: 26

I've posted a "C" version of Craig Hansen's NlogN singly-linked list
sort to net.sources.  It is titled "singly-linked list sort in C".  It
is organized as a general-purpose routine, usable to sort lists of any
node type.  It assumes that your C compiler does reasonable things with
structure layout, but this can be made compiler specific fairly easily
if your compiler is peculiar.

The main differences of this routine relative to Craig Hansen's offering
are these:

  - I've heavily commented it to make clear what is going on.
    (I did this because I didn't follow in detail what Craig's did until
     I had translated it to C and tinkered with it a little.  Craig's
     was *clear* enough, I was just a little slow...)
  - I've generalized it as mentioned above.
  - I've traded time spent moving a bookeeping pointer through the list
    against keeping a little more bookeeping information around. (The
    bookeeping space is still constant in N, however.)
  - I've included a small testing routine, so you can see if it works
    for you.

Have fun, sorting freeks, and my apologies if zillions of list sorting
routines have already been posted to net.sources.
-- 
Wayne Throop at Data General, RTP, NC
<the-known-world>!mcnc!rti-sel!dg_rtp!throopw