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}