[comp.lang.pascal] Merge sort

zig-zag@i-core.UUCP (Brian Gouge) (01/16/90)

Would someone please post the source for a merge sort routine?  Even better
if you would mail it to me personally.  I have found one example of it that
is very incomplete and makes reference to several non-existant procedures,
apparently all an integral part of merge sort itself.  I need to sort very
large disk files and apparently Merge Sort if the only answer.  Thank you
for the help.

ts@uwasa.fi (Timo Salmi LASK) (01/17/90)

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?  Even better

I far as I recall there is such a routine in O'Brien, Turbo Pascal:
The Complete Reference.  Sorry if my recall is incorrect. 

...................................................................
Prof. Timo Salmi        (Moderating at anon. ftp site 128.214.12.3)
School of Business Studies, University of Vaasa, SF-65101, Finland
Internet: ts@chyde.uwasa.fi Funet: vakk::salmi Bitnet: salmi@finfun

bigelow@hpfcso.HP.COM (Jim Bigelow) (01/17/90)

"Alogorithms + Data Structures = Programs" by N. Wirth has a section on
sorting sequential files(Sec. 2.3) that gives three types of merge sorts, 
striaght, natural, and balanced multiway; all in pascal.

Cheers,

Jim Bigelow
HP9000/S300 Pascal
Colorado Language Lab.

subbarao@phoenix.Princeton.EDU (Kartik Subbarao) (01/18/90)

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

reeder@reed.UUCP (Doug Reeder) (01/18/90)

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?  Even better

A natural merge sort appears on pp. 105-106 of "Pascal for Programmers" by
Lecarme & Nebut, McGraw-Hill 1984   ISBN 0-07-036958-5 
{capsule review: great!} I can photocopy it if you email me your address, or
better yet, mail me a stamped,self-addressed envelope.


-- 
Doug Reeder                                   USENET: ...!tektronix!reed!reeder
from ARPA: tektronix!reed!reeder@berkeley.EDU BITNET: reeder@reed.BITNET
the Little Mermaid on materialism:
"I just don't see how a world that makes such wonderful things could be bad."