Ordena Listas

Una idea poco eficiente es hacer permutaciones y checar que esté en orden:

sort(L,LO) :- 
     permuta(L,LO),
     orden(LO).

orden([A,B|T]) :-
      A < B,
      orden([B|T]).
orden([_]).

Una solución un poco mejor es insertar el elemento en el lugar que le corresponde:

sort([H|T],LO) :-
     sort(T,TO),
     inserta(H,TO,LO).
sort([],[]).

inserta(H,[],[H]).
inserta(H,[F|T],[F|R]) :-
     H > F,
     inserta(H,T,R).
inserta(H,[F|R],[H,F|R]) :-
     H =< F.

Todavía más eficiente es hacer quicksort (i.e., dividir en menores y mayores a un cierto elemento, ordenarlos y juntarlos todos).

qsort([H|T],LO) :-
    divide(H,T,Men,May),
    qsort(Men,MenO),
    qsort(May,MayO),
    append(MenO,[H|MayO],LO).
qsort([],[]).

divide(El,[H|T],[H|Men],May) :-
    El > H,
    divide(El,T,Men,May).
divide(El,[H|T],Men,[H|May]) :-
    El < H,
    divide(El,T,Men,May).
divide(_,[],[],[]).

Mejora: tener una lista intermedia que sirva de acumulador

qsort(L,LO) :- qsort(L,[],LO).

qsort([H|T],Acum,LO) :-
     divide(H,T,Men,May),
     qsort(May,Acum,MayO),
     qsort(Men,[H|MayO],LO).
qsort([],L,L).