Re: list strawman

[Ted Dennison <dennison@telepath.com>]

Jean-Marc Bourguet wrote:

> dennison@telepath.com (Ted Dennison) writes:
> 
> 
>>...OK it looks like the work involved in doing *all* the splits using
>>linear searches is (n/2 + 2(n/4) + 4(n/8) ....) where n>1. Since there
>>is one of these factors for each "level", and there are logn levels,
>>that should work out to roughly (n/2)logn, or O(n logn). So you are
>>right that it is O(N log N) worst case. However, you are wrong about
>>the best case. With a linked-list, that is *also* O(N log N).


>    procedure Split(Head: Node_Ptr; L1, L2: out Node_Ptr) is
>       Current : Node_Ptr := Head;
>       Last    : Node_Ptr := Null;
>       Other   : Node_Ptr := Null;
>    begin -- Split
>       L1 := null
>       L2 := null;
>       while Current /= null loop
>          declare
>             Next : Node_Ptr := Current.Next;
>          begin
>             Append(Current, Last, Other, L1, L2);
>             Current := Next;
>          end;
>       end loop;
>       Last.Next := null;
>       if Other /= null then
>          Other.Next := null
>       end if;            
>    end Split;
> Each split and Merge phase are O(n).  If the list is sorted, only


That's right, each call to those routines is O(n). However, for a 
mergesort you don't do just one split or merge. At the top level you do 
1, and the next level you do 2, at the next 4, and so on.

It doesn't look like the algorithm you presented does this, but then it 
doesn't look like a sort either. It only calls split once, and then 
merge. Its actually a O(n) algorithm. Too bad it doesn't actually sort, 
or you'd be up for some kind of prize. :-)

Now lets assume it *did* sort, by having split call itself recursively 
after the split if there are multiple elements, then perform a merge 
when its done. The way this modified Split algorithm works, you 
essentially do one full linear search through every list element at 
every recusion level that the list has. Since you divide the list in 
half at each level, there are log N division levels. Thus this algorithm 
you presented is O(n log n), best, worst and average case, just like I 
was saying. The algorithm I assumed for my previous mergesort split 
calculations was a bit quicker, in that I only searched through *half* 
the list at each level, but the time behavior is the same.