Ответ в теме: Сортировка слиянием на Prolog

      Комментарии к записи Ответ в теме: Сортировка слиянием на Prolog отключены
#2081

Алгоритм сортировки слиянием подробно описан и проанализирован.

merge_sort

Разделение списков в алгоритме выполняется произвольным образом. Если бы мы использовали массив — то могли бы просто поделить пополам, но со списками так не получится, мы не знаем даже их длину. Важно, чтобы длина частей была по возможности одинаковой — поэтому разделять можно на списки элементов с четными и нечетными индексами.
Функция слияния отсортированных списков была описана ранее.

mergeSort([], []):-!.
mergeSort([SingleElement], [SingleElement]):-!.
mergeSort(List, SortedList):-
  split(List, Part1, Part2),
  mergeSort(Part1, SortedPart1),
  mergeSort(Part2, SortedPart2),
  rangConcat(SortedPart1, SortedPart2, SortedList).