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 ucbjade.BERKELEY.EDU
Path: utzoo!watmath!clyde!burl!ulysses!ucbvax!ucbjade!ucblapis!oster
From: oster@ucblapis.berkeley.edu (David Phillip Oster)
Newsgroups: net.lang.c,net.lang.pascal
Subject: Re: Sorting linked lists
Message-ID: <491@ucbjade.BERKELEY.EDU>
Date: Fri, 28-Mar-86 15:38:27 EST
Article-I.D.: ucbjade.491
Posted: Fri Mar 28 15:38:27 1986
Date-Received: Tue, 1-Apr-86 05:05:43 EST
References: <165@ablnc.UUCP> <337@umcp-cs.UUCP> <402@mips.UUCP>
Sender: usenet@ucbjade.BERKELEY.EDU
Reply-To: oster@ucblapis.UUCP (David Phillip Oster)
Organization: University of California, Berkeley
Lines: 28
Xref: watmath net.lang.c:8313 net.lang.pascal:525

In article <402@mips.UUCP> hansen@mips.UUCP (Craig Hansen) writes:
>There's a simpler way, using a merge sort instead of a heap sort.
>The code below is O(n log n), and relies only on singly linked
>be fairly simple to translate.  The basic idea is to take the
>list as pairs, sorting each pair, then take pairs of sorted
>pairs and merge them together, so so on, taking geometrically
>increasing-sized lists, until you have a single sorted list.
>Craig Hansen
>MIPS Computer Systems
>...decwrl!glacier!mips!hansen
>         for ...
>		while ...
>                    i := i - 1;
>                    trailer := point;
>                    point := point^.next;
>                end {while};
>                if sublist[j] <> nil then trailer^.next := nil;
>            end {for};

Sorry guys, this is a stupid way to sort a list. Although your comaprison
function is called O(n log n), the above code is executed n^2 times.  It 
just blows the time codt to hell.  I sort my lists by copying them into an
array, sorting the array using qsort, then copying back to a list.

--- David Phillip Oster
-----------------------  ``What do you look like when you aren't visualizing?''
Arpa: oster@lapis.berkeley.edu
Uucp: ucbvax!ucblapis!oster