Path: utzoo!utgpu!jarvis.csri.toronto.edu!cs.utexas.edu!uwm.edu!rutgers!njin!princeton!phoenix!subbarao
From: subbarao@phoenix.Princeton.EDU (Kartik Subbarao)
Newsgroups: comp.lang.pascal
Subject: Re: Merge sort
Summary: Here is a merge sort program from our CS 119 Class.
Message-ID: <13005@phoenix.Princeton.EDU>
Date: 17 Jan 90 17:51:55 GMT
References: <1990Jan15.191730.5965@i-core.UUCP> <1990Jan16.211416.2300@uwasa.fi>
Lines: 63

In article <1990Jan16.211416.2300@uwasa.fi>, ts@uwasa.fi (Timo Salmi LASK) writes:
> In article <1990Jan15.191730.5965@i-core.UUCP> zig-zag@i-core.UUCP (Brian Gouge) writes:
> >Would someone please post the source for a merge sort routine?

OK -- Here Goes
------------------------------------------------------------------------
{ Linked list data types }
type
  item = ...;
  pnode = ^node;
  node =
    record
      data : item;
      next : pnode;
    end;

{ Tests whether item "x" should precede item "y" in sorted order 
  function precedes(x,y : item): boolean;
  ...}

{ Merges two nonempty lists whose first nodes are pointed to by
  "a" and "b", and returns a pointer to the head of the merged list.
  The input lists are lost, their pointers rearranged. }
function mergelists(a,b : pnode): pnode;
  var c : pnode;
  begin
    if precedes(a^.data, b^.data)
      then begin c := a; a := a^.next; end
      else begin c := b; b := b^.next; end;
    mergelists := c;
    while (a <> nil) and (b <> nil) do
      if precedes(a^.data, b^.data)
        then begin c^.next := a; c := a; a := a^.next; end
        else begin c^.next := b; c := b; b := b^.next; end;
    if (a = nil)
      then c^.next := b
      else c^.next := a
  end;

{ Sorts a nonempty list by dividing it into two sublists,
  recursively sorting the sublists, and merging the results. }
procedure mergesort(var head : pnode);
  var a,b,second : pnode;
  begin
    second := head^.next;
    if (second <> nil) then
      begin
        a := head;
        while (a^.next <> nil) do
          begin
            b := a^.next;
            a^.next := b^.next;
            a := b;
          end;
        mergesort(head);
        mergesort(second);
        head := mergelists(head,second);
      end;
  end;


-- 
subbarao@{phoenix,bogey or gauguin}.princeton.edu