На прошлой неделе мы освещали Сортировку пузырьков, помогая Снейпу с его коллекцией котлов. На этой неделе мы собираемся перейти к Брейкбиллсу и помочь Квентину Колдуотеру разобрать карты его колоды. Это не будет идеальным вариантом, и Квентин знает это. Понимаете, магия - штука непростая, и она не всегда дает желаемый результат. Но сортировка слиянием приблизит нас к разбору беспорядка колод Квентина, так что мы попробуем.

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

Вот заклинание:

Вернее, вот заклинания. Сортировка слиянием (как показали мои исследования) всегда требует двух функций, чтобы успешно отсортировать колоду карт Квентина. Причина: вам нужна одна функция для рекурсивного разделения списка на все меньшие и меньшие списки, пока каждый список не будет состоять только из одного элемента, и вам понадобится еще одна функция слияния, чтобы снова объединить отсортированные списки.

Функцию mergeSort легко объяснить. Поскольку мы хорошие фокусники (и к тому же ленивы), мы не хотим, чтобы функция возвращалась раньше, если список состоит только из одного элемента, поскольку списки из одного элемента всегда сортируются.

После этого списки, которые длиннее одного элемента, должны быть разделены на две части, сначала найдя среднюю точку, а затем разделив список на две разные переменные.

Наконец, мы рекурсивно вызываем mergeSort функцию в другой merge функции, которая принимает два аргумента, левую и правую часть списка.

Функция слияния

Функция слияния немного сложнее, но совсем немного.

Смысл функции merge состоит в том, чтобы взять разделенные списки и снова объединить их вместе, отсортированные от наименьшего к наибольшему. Для этого требуется цикл while, который сначала проверяет, есть ли длина как у левого, так и у правого списков. Если бы одна сторона этого не сделала, не было бы необходимости сортировать. Мы также можем предположить, что оставшаяся часть уже будет отсортирована, поскольку mergeSort рекурсивно вызывается на всем пути.

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

Мы делаем наоборот, если левый боковой элемент больше правого.

Наконец, остаток обоих списков объединяется. Это работает просто потому, что мы знаем, что если один список был очищен и поскольку оба списка уже отсортированы, оставшиеся элементы больше, чем те, которые уже находятся в массиве результатов в порядке возрастания.

Заключение

Так мы узнали, как сортировать карточки Квентина.

Не верите мне? Возьмите приведенный выше код и вставьте следующее:

mergeSort([4, 2, 3, 5, 1, 7, 8, 10, 9, 6])

Это отсортировано? Я так и думал. Квентин хочет выучить лучшие, более мощные заклинания, чтобы облегчить его проблемы с сортировкой. В следующий раз мы рассмотрим двоичный поиск, теперь, когда у нас есть все карточки Квентина, отсортированные.