/* pipe-line merge sorter */

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

pipe(X,Y) :-
	lap(X,XX),
	mergeAll(XX,Y).

mergeAll([Single],Single) :- !.
mergeAll(S,Out) :-
	merge2(S,Out1),mergeAll(Out1,Out).

merge2([],[]).
merge2([Single],[Single]).
merge2([A,B|T],[YY|Y]) :-
	merge(A,B,YY),
	merge2(T,Y).

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

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