Ответ в теме: Сортировка слиянием на 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).