The simplest way to code a sort in Prolog is to describe what a sorted list looks like. A sorted list is a permutation of some given list such that elements that appear earlier in the list are smaller than elements that appear later in the list. In SWI Prolog:

srt(X,Y):- permutation(X,Y), isSrt(Y). isSrt([]). isSrt([_]). isSrt([H,I|J]):- H=<I, isSrt([I|J]).

The beauty of this solution is that Prolog does all the dirty work of finding a sorted `Y` for our given `X`. The darker side is that Prolog’s satisfaction mechanism carries out a brute force search through all possible permutations of the given list. This is dangerous; compare the runtimes of our naive sort and the Prolog built-in sort (which is decidedly less naive):

%5 seconds vs. something < 0.01 secondsreverse([1,2,3,4,5,6,7,8,9,10],X), profile(srt(X,Y)). reverse([1,2,3,4,5,6,7,8,9,10],X), profile(msort(X,Y)).

Not great, and notice how fast the worst case time of O(n!) grows:

%55 seconds vs. something < 0.01 secondsreverse([1,2,3,4,5,6,7,8,9,10,11],X), profile(srt(X,Y)). reverse([1,2,3,4,5,6,7,8,9,10,11],X), profile(msort(X,Y)).

This is to be expected; if we want to be picky about how the job gets done, we can be more explicit in our description. So let’s ignore performance and and see how to write a declarative “permutation” predicate from scratch.