====== Insert sort ======
{{tag>sorting algorithms recursion}}
===== Description =====
Prolog implementation of insert sort based on idea of accumulator.

**Source**:  Guide to Prolog Programming (on-line tutorial)
===== Download =====
Program source code: {{insert_sort.pl}}
===== Listing =====
<code prolog>
insert_sort(List,Sorted):-i_sort(List,[],Sorted).
i_sort([],Acc,Acc).
i_sort([H|T],Acc,Sorted):-insert(H,Acc,NAcc),i_sort(T,NAcc,Sorted).
   
insert(X,[Y|T],[Y|NT]):-X>Y,insert(X,T,NT).
insert(X,[Y|T],[X,Y|T]):-X=<Y.
insert(X,[],[X]).</code>
===== Comments =====