/* pipe-line merge sorter */

test :- lap([10,5,3,1,7,2,4,6,5,100,5,12,150], X),
	pipe(X),
	#write(X).

lap(In,Out) :- In=[],Out=[].
lap(In,Out) :- In=[X|L],Out=[[X]|S],
	lap(L,S).

pipe(In) :- In=[I],In<-I,!.
pipe(In) :- mergeProcess(In) && pipe(In).

mergeProcess([]) :-!.
mergeProcess([In]) :- In<-In,!.
mergeProcess(In) :- In=[A,B|T],
    merge(A,B,X),fin(In=[X|T]),
    mergeProcess(T).

merge(X,Y,Z) :- Y=[],!,Z<-X.
merge(Y,X,Z) :- Y=[],!,Z<-X.
merge([A|X],[B|Y],[C|Z]) :-
	A =< B,!, C<-A,
	merge(X,[B|Y],Z).
merge([A|X],[B|Y],[C|Z]) :-
	B =< A,!, C<-B,
	merge([A|X],Y,Z).