Если вы не знакомы с рекурсией, пожалуйста, прочтите сообщение прошлой недели [Рекурсия, прелюдия к сортировке слиянием](https://medium.com/@young.scottw/recursion-a-prelude-to-merge-sort- ff0ee0938d2c). Сделанный? Хорошо, тогда давайте сразу к делу. Как и было обещано, на этой неделе мы попытаемся реализовать алгоритм сортировки слиянием в Ruby. Это проверит наше понимание материала, который мы узнали в посте о рекурсии на прошлой неделе.
Сортировка слиянием — это хрестоматийный пример алгоритма «разделяй и властвуй». Идея в том, что мы «делим» сортируемый массив на два подмассива половинного размера. Затем «победите» проблему, рекурсивно отсортировав два подмассива с помощью алгоритма сортировки слиянием. Наконец, мы снова объединяем два отсортированных подмассива, создавая отсортированное решение. Это может показаться немного запутанным, но по мере нашего продвижения в этом будет больше смысла.
Изображение ниже, мы надеемся, прояснит некоторую путаницу.
В верхней части изображения у нас есть несортированный массив. Мы спускаемся к одноэлементным массивам, рекурсивно вызывая нашу функцию сортировки слиянием. Базовый случай, помните, что у каждого рекурсивного алгоритма должен быть базовый случай, когда мы достигаем одноэлементных массивов. Затем мы можем начать сравнивать элементы и объединять их вместе. Давайте посмотрим на код.
Обратите внимание на базовый случай, arr размера 1. Также обратите внимание на два четких шага. Во-первых, «разделить», если длина не равна 1, разделить массив и снова рекурсивно вызвать merge_sort с двумя новыми массивами. Затем «побеждайте», снова сливаясь воедино. Мы еще не написали алгоритм слияния, но не волнуйтесь, мы это сделаем.
Так как же нам реализовать алгоритм слияния? Это довольно просто, но давайте пройдемся по нему. К тому времени, когда мы впервые вызываем нашу функцию слияния, мы имеем массивы размером 1, это значительно упрощает работу, которую мы делаем, а также помогает нам немного легче понять алгоритм. На этом этапе мы просто сравниваем наши два одноэлементных массива и помещаем их в отсортированный массив в соответствующем порядке. Легко, верно?
Та небольшая сложность, которая существует в алгоритме слияния, возникает, когда мы начинаем рассматривать массивы размером больше единицы. Хотя это тоже не очень сложно. Мы просто повторяем вышеуказанные шаги до тех пор, пока либо левый подмассив, либо правый подмассив не станет пустым, а затем помещаем все оставшиеся элементы в конец отсортированного массива. Давайте посмотрим это в действии ниже.
Довольно круто! Мы создаем пустой массив для последующего возврата. Затем мы помещаем элементы в этот массив по порядку, пока один из двух входных массивов не станет пустым. Наконец, мы просто объединяем все, что осталось, с отсортированным массивом и неявно возвращаем его. Эта последняя строка может выглядеть немного странно, мы могли бы переставить ее и объединить правый массив, а затем левый массив, это не будет иметь никакого значения, так как один из двух массивов все равно должен быть пустым.
Вот она, реализованная на ruby версия сортировки слиянием. Не углубляясь в математику, поговорим о сложности алгоритма. Большинство алгоритмов «разделяй и властвуй» будут иметь сложность порядка log n, из этого правила, как и для большинства правил, есть исключения. При сортировке слиянием мы получаем O(n log n). В основном разделение массивов — это операция O (n), а объединение массивов обратно в окончательное решение — операция O (log n). В результате получается O(n log n) наихудший случай. Я знаю, что это не очень удовлетворительный анализ, но математика, связанная с настоящим анализом этого алгоритма, выходит за рамки этой статьи.
Спасибо за прочтение. Ниже приведены несколько ссылок, если вы хотите изучить дополнительные материалы, касающиеся сортировки слиянием.
