%	Insertion sort

insertion_sort(X, Y) :- isort(X, [], Y).

isort([X|Y], L1, L3) :-
	insert(X, L1, L2),
	isort(Y, L2, L3).
isort([], L, L).

insert(A, [B|C], [A, B|C]) :-
	A <= B, !.
insert(A, [B|C], [B|D]) :-
	insert(A, C, D).
insert(A, [], [A]).



%	Quicksort program.
%	NOTE: '<' works for atoms as well as numbers

quick_sort(L0, L) :- qsort(L0, L, []).

qsort([X, ..L], R, R0) :- !,
	partition(L, X, L0, L1), 
	qsort(L1, R1, R0), 
	qsort(L0, R, [X, ..R1]).
qsort([], R, R).

partition([X, ..L], Y, [X, ..L0], L1) :-
	X < Y, !,
	partition(L, Y, L0, L1).
partition([X, ..L], Y, L0, [X, ..L1]) :- !,
	partition(L, Y, L0, L1).
partition([], _, [], []).


%---------------------------------------------------------------%
%	Perform a natural merge sort on a list of values.	%
%	Most suitable for `nearly' sorted input lists.		%
%---------------------------------------------------------------%

merge_sort(In,Out):-
	split_pass(In,Mid),
	merge_pass(Mid,Out).

%
%	Make a super-list of ascending subsequences
%
split_pass([],[]):- !.
split_pass([A],[[A]]):- !.
split_pass([A,B|T],[[A|F]|R]):-
	A < B,
	!,
	split_pass([B|T],[F|R]).
split_pass([A,B|T],[[A]|R]):-
	split_pass([B|T],R).

%
%	Merge the elements of a super-list into single ordered list
%
merge_pass([] , []) :- !.
merge_pass([A],  A) :- !.
merge_pass([A,B],M) :-
	!,
	merge(A,B,M).
merge_pass([A,B|T], M) :-
	merge(A,B,AB),
	merge_pass(T,TM),
	merge(AB,TM,M).

%
%	Merge two ordered lists into a single ordered list
%
merge([],L,L):- !.
merge(L,[],L):- !.
merge([A|AT],[B|BT],[A|MT]):-
	A < B,
	!,
	merge(AT,[B|BT],MT).
merge(L,[B|BT],[B|MT]):-
	merge(L,BT,MT).
