Merge Sort

home1 home2
and the


A not very imaginative pfl version of merge sort:

let rec
 eoi = -999,

 L =5::6::7::19::15::12::13::0::1::4::
 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
   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,


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.

Coding Ockham's Razor, L. Allison, Springer

A Practical Introduction to Denotational Semantics, L. Allison, CUP

free op. sys.
free office suite
~ free photoshop
web browser

|   choice
|| parallel
-> sequence
? input act
! output act
chan new channel

© L. Allison   (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.