// Merge sort
MS(ret) >< [] => ret~[];
MS(ret) >< x:xs => MS_tail(ret, x)~xs;

MS_tail(ret, n) >< [] => ret~(*R)[n];
MS_tail(ret, int n) >< x:xs => 
//	MS(a)~left, MS(b)~right, Append(ret,a)~b,
//	Split(0, left,right) ~ (n:x:xs);
	MS(a)~left, MS(b)~right, Append(ret,a)~b,
	(*L)Split(left,right) ~ (*R)(n:x:xs);


/*
Splitn(int flag, a, b) >< [] => a~[], b~[];
Splitn(int flag, a, b) >< (int y):ys
| flag==0 => b~(*R)(y:cnt), (*L)Splitn(1, a, cnt)~ys
| _       => a~(*R)(y:cnt), (*L)Splitn(0, cnt, b)~ys;

Split(a,b) >< x:xs => Splitn(0,a,b)~x:xs;
*/

Split(a,b) >< [] => a~[], b~[];
Split(a,b) >< x:xs => a~(x:cntl), (*L)Split(b,cntl)~xs;



// この実験から、Merge は悪くないことがわかる。
// Part でも -t 5 6 7 順に速くなる。
// つまり、Split が悪いと言える。

/*
MS_tail(ret, n) >< [] => ret~(*R)[n];
MS_tail(ret, n) >< x:xs => 
	MS(a)~left, MS(b)~right, Merge(ret,b)~a,
	(*L)Split(left,right) ~ (*R)(n:x:xs);
*/

Merge(ret, snd) >< [] => ret~snd;
Merge(ret, snd) >< x:xs => (*L)MergeCC(ret, x, xs)~snd;

MergeCC(ret, int y, ys) >< [] => ret~(*R)(y:ys);
MergeCC(ret, int y, ys) >< (int x):xs
| x <= y => ret~(x:cnt), (*L)MergeCC(cnt, y, ys) ~ xs
| _      => ret~(y:cnt), (*L)MergeCC(cnt, x, xs) ~ ys;
// ret~(*R)(x:cnt) less improvement

// *** I should make an option that outputs bytecodes to a file. ***
// *** Then, I have to look the reason why 
// *** ret~(*R)(x:cnt), MergeCC(cnt, y, ys) ~ xs becomes less improvement.




//	left~cntr, (*L)Split(cntr,cntl)~xs, right~(x:cntl);
// This also make it less efficient.


const LIST_ELEM=1200000;

MkRandList(ret) >< (int n)
| n>0 => ret~(rd:cnt), (*L)MkRandList(cnt)~(n-1) 
  where rd=rand(LIST_ELEM)
| _ => ret~[];

MkRandList(cnt)~(LIST_ELEM),
MS(ret)~cnt;
ret;