Ответ в теме: Сортировка вставками (методом простого включения)

      Комментарии к записи Ответ в теме: Сортировка вставками (методом простого включения) отключены
#2143

Для реализации сортировки понадобится функция вставки элемента в упорядоченный список:

insert(Element, [], [Element]):-!.
insert(Element, [Head|Tail], [Element, Head|Tail]):-
  Element < Head, !.
insert(Element, [Head|Tail], [Head|InsertTail]):-
  insert(Element, Tail, InsertTail).

Если исходный список пуст, то результатом является список из вставляемого элемента.
Если первый элемент списка меньше вставляемого – новый элемент добавляется в начало списка. Чтобы сортировать по убыванию – достаточно изменить оператор сравнения.
В остальных случаях от списка отделяется первый элемент, остальные обрабатываются рекурсивно (где-то между ними будет добавлено новое значение). К полученному результату добавляется ранее вытащенный первый элемент.

Согласно алгоритма, исходный список разделяется на две части – упорядоченную и необработанную. Изначально в отсортированной части нет элементов, для такой инициализации можно написать вспомогательную функцию:

insertion_sort(List, SortedList):-
  insertion_sort(List, [], SortedList).

insertion_sort([], SortedList, SortedList):-!.
insertion_sort([Head|Tail], SortedPart, SortedList):-
  insert(Head, SortedPart, SortedPartWithHead),
  insertion_sort(Tail, SortedPartWithHead, SortedList).

Если элементы в необработанной части закончились – функция возвращает упорядоченную часть в качестве результата.
В противном случае первый элемент неупорядоченной части вставляется в отсортированную при помощи функции insert. Полученный в результате список обрабатывается рекурсивно.