В настоящее время я пишу код в основном на JavaScript и счел необходимым решить одну из самых сложных проблем с кодом, с которыми я недавно сталкивался. В этой задаче используется рекурсия — процесс, который меня иногда пугает. Давайте займемся этим!

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

Сортировка слиянием – это эффективный алгоритм сортировки на основе сравнения. Сортировка слиянием использует стратегию разделяй и властвуй. Я украл прикольную маленькую гифку из википедии и вставил слева

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

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

3. На этом шаге мы проверяем, является ли 5 is less than 3, и помещаем меньшее значение из двух в наш отсортированный массив — в данном случае lowestRight i.e. 3. Затем сдвигаем наш указатель lowestRight вправо и снова проверяем.

4. Затем мы проверяем, является ли 5 is less than 10, и снова помещаем меньшее значение из двух в наш отсортированный массив — на этот раз lowestLeft i.e. 5. Затем сдвигаем наш указатель lowestLeft вправо и снова проверяем. Мы повторяем этот процесс, пока наши указатели не достигнут конца соответствующих массивов.

5. Мы продолжаем повторять этот процесс до тех пор, пока наш sortedArray не будет заполнен (есть еще один вариант этого решения, когда мы передаем копию массива и используем ее, чтобы помочь нам отсортировать наш исходный массив на месте, однако я временно игнорирую это!)

Давайте попробуем его закодировать!

Итак, что здесь происходит? В основном то, что мы только что описали выше! Единственная сложная часть заключается в том, что мы используем рекурсию для достижения нашей цели. Я шаг за шагом пройдусь по большей части кода, объясняя каждый шаг и используя псевдокод для акцентирования внимания… как однажды сказал известный итальянский сантехник:

Поехали!

Когда мы делаем наш первый вызов, это вызывает множество рекурсивных вызовов, которые не останавливаются до тех пор, пока не будет выполнен наш вариант возврата:

В приведенном выше коде сначала мы вызываем mergeSort(arr) для массива, который хотим отсортировать. В этом вызове длина массива не равна 1, поэтому мы разрезаем массив пополам и отправляем обе половины в…

mergeSortedArrays(mergeSort([9, 5, 3]), mergeSort([10, 5, 6, -1]))

Затем эта строка выполняет два рекурсивных вызова mergeSort(), и снова наш критический случай не выполняется, поскольку эти массивы имеют длину 3 и 4 соответственно. Таким образом, этот вызов добавляется в стек, массивы снова делятся пополам, и выполняются еще 3 рекурсивных вызова, которые добавляются в стек.

Обратите внимание, как я сказал, что 3 вызова были добавлены в стек вызовов. Это связано с тем, что для mergeSort([9]) был выполнен критический случай, длина этого массива равна 1. Этот вызов возвращает [9], а затем ожидает возврата mergeSort([5, 3]).

mergeSortedArrays(mergeSort([9]), mergeSort([5, 3]))

mergeSortedArrays(mergeSort([10, 5]), mergeSort([6, -1]))

Наконец, mergeSort() вызывается еще 6 раз, чтобы разбить оставшиеся массивы длины 2 на массивы длины 1.

Собираем все обратно

Теперь, когда мы разбили наш массив на 7 отдельных крошечных массивов, мы можем начать собирать их вместе!

  1. Мы объединяем только что возвращенные значения из стека вызовов [6] и [-1] и отправляем их в новый массив по порядку с помощью нашей вспомогательной функции mergeSortedArrays([6], [-1]), после чего возвращается этот новый массив. =>[-1, 6]
  2. Затем мы переходим к нашему следующему вызову стека, который возвращается: [10] и [5] мы отправляем эти два значения в нашу вспомогательную функцию mergeSortedArrays([10], [5]) и возвращаем массив =>[5, 10]
  3. Следующие вызовы извлекаются из стека вызовов, потому что они также встретили свой критический случай — mergeSortedArrays([5],[3]) вызывается для двух массивов, [5] and [3]возвращенных из mergeSort(), возвращающих =>[3, 5]
  4. Затем мы приходим к другому вызову в стеке вызовов, который теперь может разрешаться: mergeSortedArrays(mergeSort([9]), mergeSort([5, 3])) теперь мы знаем, что mergeSort([5, 3]) вернет [3, 5] и что mergeSort([9]) вернет [9]. Это означает, что мы можем вызвать нашу вспомогательную функцию с этими возвращенными значениями и объединить их в упорядоченном виде. множество! mergeSortedArrays(mergeSort([9]), mergeSort([5, 3])) вернется =>[3, 5, 9]

Этот процесс повторяется до тех пор, пока наш последний рекурсивный вызов не будет разрешен, возвращая наш отсортированный массив!

Фуф. Ты усталый? Я устал. Я также благодарен, что большинство современных языков программирования уже реализуют очень эффективные sort() функции прямо из коробки!

При этом по-прежнему важно понимать концепции, которые реализует этот алгоритм сортировки, надеюсь, вам понравилось это путешествие по mergeSort() переулку.

Ваше здоровье!