Re: list strawman

[Jean-Marc Bourguet <jm@bourguet.org>]

dennison@telepath.com (Ted Dennison) writes:

> Jean-Marc Bourguet <jm@bourguet.org> wrote in message news:<3c3bfabc$0$3190$626a54ce@news.free.fr>...
> > Ted Dennison<dennison@telepath.com> writes:
> > 
> > > That's a good point. It would probably be fairly easy to alternate
> > > which side the pivot is taken from.
> > 
> > This will not change the behaviour in N^2 for a (nearly) sorted input.
> 
> After thinking about it harder, you are right. Everything will allways
> go on one side of the pivot, no matter which side you take it from. So
> no "dividing" will actually happen, which is where this
> divide-and-conquer algorithm gets its speed from.
> 
> > > I believe the splitting part of mergesort would involve a linear
> > > search for a linked-list. That would take us into O(n*2) territory,
> > > if not worse. In my student days I could figure out the exact
> > > factor...hmmm...perhaps its just another nlogn...
> > 
> > Merge sort can be implemented in O(N log N) worst case, with a O(N)
> > for an already sorted input.
> 
> OK. By arguing through repeated assertion, you are forcing to either
> ignore you, or do the work of proof myself. Since I made the first
> claim, its only fair that I do the work I guess...

I think the proof is in The Art Of Computer Programming (Knuth, volume
three).

> ...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).

Not tested, not even compiled, but it should show the principles.  I
think it is in the section "external sorting" of Knuth.  I think the
sort is stable which is an added bonus (but this should be verified).

type Node;   
type Node_Ptr is access Node;
type Node is record
   Next: Node_Ptr;
   Value: Value_Type;
end record;

procedure Sort (Head : in out Node_Ptr) is

   procedure Append(N : Node_Ptr; 
                    Last, Other: in out Node_Ptr;
                    L1, L2: out Node_Ptr) is
   begin
      if Last = null then
         Last := N;
         L1   := N;
      else if Last.Value <= N.Value then
         Last.Next := N;
         Last := N;
      else if Other = null then
         Other := Last;
         Last  := N;
         L2    := N;
      else
         declare
           Tmp : Node_Ptr := Last;
         begin
           Last := Other;
           Other := Tmp;
           Last.Next := N;
           Last := N;
         end;
      end if;
   end Append;

   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;

   procedure Merge(L1, L2: in out Node_Ptr) is
      Current1 : Node_Ptr := L1;
      Current2 : Node_Ptr := L2;
      Last    : Node_Ptr := null;
      Other   : Node_Ptr := Null;
      Tmp     : Node_Ptr := Null;
   begin -- Merge
      L1 := null;
      L2 := null;
      while Current1 /= null and Current2 /= null loop
         if Current1.Value <= Current2.Value then
            declare
               Next : Node_Ptr := Current1.Next;
            begin
               Append(Current1, Last, Other, L1, L2);
               Current1 := Next;
            end;
         else
            declare
               Next : Node_Ptr := Current2.Next;
            begin
               Append(Current2, Last, Other, L1, L2);
               Current2 := Next;
            end;
         end if;
      end loop;
      if Current1 /= null then
         Tmp := Current1;
      else
         Tmp := Current2;
      end if;
      while Tmp /= null loop
         declare
            Next : Node_Ptr := Tmp.Next;
         begin
            Append(Tmp, Last, Other, L1, L2);
            Tmp := Next;
         end;
      end loop;
      Last.Next := null;
      if Other /= null then
         Other.Next := null
      end if;                     
   end Merge;

begin -- Sort
   if Head = Null then
      return;
   end if;
   Split(Head, L1, L2);
   while L2 /= Null loop
      Merge(L1, L2);
   end loop;
   Head = L1;
end Sort;

Each split and Merge phase are O(n).  If the list is sorted, only
Split is done.  Merge reduce the number of chunks by a factor 2 and
there is at most N chunks (if the list is in the reverse order), so
worse case is O(N log N).

-- 
Jean-Marc