Sorting linked lists

[Craig Hansen]

> 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

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"