Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!watmath!clyde!burl!ulysses!gamma!epsilon!zeta!sabre!petrus!bellcore!decvax!decwrl!glacier!mips!hansen
From: hansen@mips.UUCP (Craig Hansen)
Newsgroups: net.lang.c,net.lang.pascal
Subject: Re: Sorting linked lists
Message-ID: <423@mips.UUCP>
Date: Sun, 30-Mar-86 19:50:46 EST
Article-I.D.: mips.423
Posted: Sun Mar 30 19:50:46 1986
Date-Received: Wed, 2-Apr-86 01:01:30 EST
References: <165@ablnc.UUCP> <337@umcp-cs.UUCP> <402@mips.UUCP> <491@ucbjade.BERKELEY.EDU>
Organization: MIPS Computer Systems, Sunnyvale, CA
Lines: 67
Xref: watmath net.lang.c:8324 net.lang.pascal:526

> 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

David, you can sort your lists anyway stupid way you god-damn please.  ~==~
The code you excerpt above is NOT executed n^2 times, it's
executed O(n log n) times. Try profiling it if you can't reason it out.

To explain further, the outer-most loop is executed O(log n) times:
    
    MergeLength := 1;
    while MergeLength < SymbolCount do begin
        ...
        MergeLength := MergeLength * 2;
    end {while};
	
The inner loop is order n; even though it is composed of nested loops:

	point := table;
	while point <> nil do begin
	    ...
	end {while};

executes n/MergeLength times, and the loop:

                i := MergeLength;
                while (point <> nil) and (i > 0) do begin
                    i := i - 1;
		    ...
		end {while};

executes MergeLength times; the end result is O(n).  Another way of seeing
this is by noting that the inner loop moves "point" through the list exactly
once.

Did I lose anybody?

-- 

Craig Hansen			|	 "Evahthun' tastes
MIPS Computer Systems		|	 bettah when it
...decwrl!mips!hansen		|	 sits on a RISC"