Sorting linked lists

[David Phillip Oster]

In article <402 at mips.UUCP> hansen at 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 at lapis.berkeley.edu
Uucp: ucbvax!ucblapis!oster