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