На этом шаге мы рассмотрим этот метод сортировки.
В основе сортировки слиянием лежит замечание, согласно которому слияние двух отсортированных списков выполняется быстро.
Список из одного элемента уже отсортирован, поэтому сортировка слиянием разбивает список на одноэлементные "куски", а затем последовательно выполняет их слияние.
Приведем несколько демонстрационных примеров.
-- Демонстрация сортировки методом двухпоточного слияния -- ***************************************************** -- Функция, объединяющая элементы двух числовых списков -- lst и lst1, элементы которых отсортированы по возрас- -- танию, в упорядоченный по возрастанию список (двухпо- -- точное слияние) ------------------------------- merge1:: [Int] -> [Int] -> [Int] merge1 lst lst1 | null lst = lst1 | True = insert (head lst) (merge1 (tail lst) lst1) ------------------------------------------------------------ -- Функция, помещающая элемент b в отсортированный по воз- -- растанию список LST с сохранением его упорядоченности -------------------------------------------------------- insert:: Int -> [Int] -> [Int] insert b lst | null lst = [b] | b<=head lst = b : lst | True = head lst : insert b (tail lst) -- ******************************************************** -- Неудачные тестовые примеры: --------------------------------------------------------- test = merge1 [1,3,5,7] [4,6,8] == [1,3,4,5,6,7,8] && merge1 [1,5,8,9] [10,23,54] == [1,5,8,9,10,23,54] && merge1 [1,5,8,9] [2,3,8,9,45] == [1,2,3,5,8,8,9,9,45]
На следующем шаге мы рассмотрим быструю сортировку.
