%Insertion sort implementation in prolog.

%Misc programs
lt(E1,E2) :- E1<E2.

%Insert fn, important.
insert(X,[],[X]).
insert(X,L,OList) :-
	append(Tmp,[Y],L),
	lt(X,Y),
	insert(X,Tmp,OL2),
	append(OL2,[Y],OList).

insert(X,L,OList) :-
	append(Tmp,[Y],L),
	not(lt(X,Y)),
	append(L,[X],OList).


%Driver fn.
insort([],[]).
insort(L,OrderList) :-
	append(Tmp,[X],L),
	insort(Tmp,OL2),
	insert(X,OL2,OrderList).

%Reverse a list
revlist([],[]).
revlist([H|T1],RL) :- revlist(T1,T2),append(T2,[H],RL).

revinsort(L,OrderList) :- revlist(L,L2),insort(L2,OrderList).