# Merge Sort

 home1 home2  Bib  Algorithms  Bioinfo  FP  Logic  MML  Prog.Lang and the  Book

FP
PFL
Examples
Syntax

A not very imaginative pfl version of merge sort:

 ```let rec eoi = -999, L =5::6::7::19::15::12::13::0::1::4:: 3::2::8::18::17::16::9::10::11::14::nil, LU=0::1::2::3::4::5::6::7::8::9::nil, LD=9::8::7::6::5::4::3::2::1::0::nil, {data sets} listtochan = lambda L. lambda ch. if null L then ch!eoi -> stop else ch!hd L -> listtochan tl L ch, split = lambda inch. lambda out1. lambda out2. let rec {alternate elements from inch go to each output channel} flip = lambda out1. lambda out2. inch?x -> if x=eoi then out1!eoi -> stop || out2!eoi -> stop else out1!x -> flip out2 out1 in flip out1 out2, merge = lambda in1. lambda in2. lambda outch. let rec copy = lambda inch. inch?x -> outch!x -> if x=eoi then stop else copy inch, f = lambda x. lambda y. {NB. x<>eoi or y<>eoi} if x=eoi then outch!y -> copy in2 else if y=eoi then outch!x -> copy in1 else if x in1?z -> f z y else outch!y -> in2?z -> f x z in in1?x -> in2?y -> f x y | in2?y -> in1?x -> f x y, msort = lambda inch. lambda outch. inch?x -> inch?y -> if y=eoi then outch!x -> outch!eoi -> stop else let a=chan, b=chan, c=chan, d=chan in a!x -> b!y -> split inch a b || msort a c || msort b d || merge c d outch, c=chan in listtochan L c || msort c output {\fB Parallel Merge Sort. \fP} ```
example c1993.

Note the use of a "special" value, eoi, to indicate the end of transmission on a channel.

 let rec eoi = -999, L =5::6::7::19::15::12::13::0::1::4:: 3::2::8::18::17::16::9::10::11::14::nil, LU=0::1::2::3::4::5::6::7::8::9::nil, LD=9::8::7::6::5::4::3::2::1::0::nil, {data sets} listtochan = lambda L. lambda ch. if null L then ch!eoi -> stop else ch!hd L -> listtochan tl L ch, split = lambda inch. lambda out1. lambda out2. let rec {alternate elements from inch go to each output channel} flip = lambda out1. lambda out2. inch?x -> if x=eoi then out1!eoi -> stop || out2!eoi -> stop else out1!x -> flip out2 out1 in flip out1 out2, merge = lambda in1. lambda in2. lambda outch. let rec copy = lambda inch. inch?x -> outch!x -> if x=eoi then stop else copy inch, f = lambda x. lambda y. {NB. x<>eoi or y<>eoi} if x=eoi then outch!y -> copy in2 else if y=eoi then outch!x -> copy in1 else if x in1?z -> f z y else outch!y -> in2?z -> f x z in in1?x -> in2?y -> f x y | in2?y -> in1?x -> f x y, msort = lambda inch. lambda outch. inch?x -> inch?y -> if y=eoi then outch!x -> outch!eoi -> stop else let a=chan, b=chan, c=chan, d=chan in a!x -> b!y -> split inch a b || msort a c || msort b d || merge c d outch, c=chan in listtochan L c || msort c output {\fB Parallel Merge Sort. \fP}
 Coding Ockham's Razor, L. Allison, Springer A Practical Introduction to Denotational Semantics, L. Allison, CUP

 Linux  Ubuntu free op. sys. OpenOffice free office suite The GIMP ~ free photoshop Firefox web browser

pfl...
 | || choice parallel sequence input act output act new channel

 © L. Allison   http://www.allisons.org/ll/   (or as otherwise indicated), Faculty of Information Technology (Clayton), Monash University, Australia 3800 (6/'05 was School of Computer Science and Software Engineering, Fac. Info. Tech., Monash University, was Department of Computer Science, Fac. Comp. & Info. Tech., '89 was Department of Computer Science, Fac. Sci., '68-'71 was Department of Information Science, Fac. Sci.) Created with "vi (Linux + Solaris)",  charset=iso-8859-1,  fetched Wednesday, 08-Feb-2023 11:23:12 AEDT.