[Back to SORTING SWAG index]  [Back to Main SWAG index]  [Original]

{
GREGORY P. SMITH

> Well, that's easier said than done !  So far I've accomplished a
> selection sort which takes about 10-15 minutes For 1000 Records, and I'm
> gonna be needin to sort about 5000 For the Programz intended application
> !!! Also the place that I'm writing this For has an 8088 With 640K RAM
> <chuckle> !!! Could you pleez tell me how to do a merge sort <is that
> easier than quicksort

Here is an example followed by an exlpanation.
}

Type
  ListPtr = ^List;
  List = Record
    next : ListPtr; { next node }
    str  : String;  { data to sort }
  end;

{ Splits List l into two half lists, h1 & h2 }
Procedure SplitList(l : ListPtr; Var h1, h2 :  ListPtr);
Var
  listone : Boolean;
  tmp : ListPtr;
begin
  h1 := nil;
  h2 := nil;
  listone := True;            { start With first list }
  While l <> nil do
  begin
    tmp := l^.next;           { save next node to split }
    if listone then
    begin                     { insert a node in the first list }
      l^.next := h1;
      h1 := l;                { keep h1 at head }
    end
    else
    begin                     { insert a node in the second list }
      l^.next := h2;
      h2 := l;                { keep h2 at head }
    end;
    l := tmp;                 { move to next node }
    listone := not listone;   { alternate lists to insert into }
  end;
end; { SplitList }

{----------------- Merge Sort -------------------}

{ merges sorted l1 & l2 into one sorted list (alphabetically) }
Function MergeAlphaLists(l1, l2 : ListPtr) : ListPtr;
Var
  tmp : ListPtr;  { resulting list }
begin
  if (l1 = nil) then
    tmp := l2
  else
  if (l2 = nil) then
    tmp := l1
  else
  if l1^.str < l2^.str then
  begin { lesser node first }
    tmp := l1;
    l1 := l1^.next;
  end
  else
  begin
    tmp := l2;
    l2 := l2^.next;
  end;
  MergeAlphaLists := tmp;               { return head of merged sorted list }
  While (l1 <> nil) and (l2 <> nil) do  { traverse lists }
  if l1^.str < l2^.str then
  begin
    tmp^.next := l1; { add the lesser node }
    tmp := l1;       { move ahead }
    l1 := l1^.next;  { next node }
  end
  else
  begin
    tmp^.next := l2; { add the lesser node }
    tmp := l2;       { ahead 1 }
    l2 := l2^.next;  { next node }
  end;
  if (l1 <> nil) then
    tmp^.next := l1   { append remaining nodes }
  else
    tmp^.next := l2;
end; { MergeAlphaLists }

{ Sorts list l alphabetically }
Function MergeSortAlpha(l : ListPtr) : ListPtr;
Var
  sl1,
  sl2 : ListPtr;
begin
  if l <> nil then                 { empty list? }
    if l^.next <> nil then
    begin   { single node list? }
      inc(progress);
      SplitList(l, sl1, sl2);      { split list into two halves }
      sl1 := MergeSortAlpha(sl1);  { sort the first half }
      sl2 := MergeSortAlpha(sl2);  { sort the second half }
      MergeSortAlpha := MergeAlphaLists(sl1, sl2)  { combine sorted lists }
    end
    else
      MergeSortAlpha := l   { single node is already sorted }
  else
    MergeSortAlpha := nil
end;

{
What mergesort does is to split the list into two equal halves.  It then
mergesorts each of these halves, and merges them back together.  The Real work
is done in the merging step.  When the lists are split down to the level of
single node lists they are merged together again in the correct order.  As it
pops out of the recursion the larger lists are sorted so that merging will
still keep them in order because each node is > than the previous one.  This is
probably the most widely used sorting algorithm (don't quote me) because it is
simple but delivers n*log(n) performance like any good algorithm would.
}

[Back to SORTING SWAG index]  [Back to Main SWAG index]  [Original]