Сортировка - это базовый и чрезвычайно важный компонент изучения алгоритмов. Многие другие / более высокие алгоритмы полагаются на отсортированные списки для лучшей работы, поэтому размещение вещей в правильном порядке создает основу для решения многих проблем. Мы собираемся пропустить более прямую сортировку вставкой и выбором и перейдем к тому, что работает немного лучше: сортировке слиянием.

Вставка, выделение и даже быстрая сортировка имеют квадратичный большой знак "О" в худшем случае (n ²). Часы сортировки слиянием лучше O (n log n) из-за его парадигмы «разделяй и властвуй». Этот тип сортировки работает путем деления исходного массива на два массива, которые он затем объединяет после их сортировки, также разделяя эти массивы и эти массивы, пока не найдет коллекции отдельных элементов, которые он сравнивает и объединяет, а затем возвращается обратно до последней рекомбинации. Если это звучит как рекурсия, то это так!

Так как часть деления уменьшает вдвое общую длину массива, а затем вдвое и т. Д., Пока мы не достигнем единицы, временные затраты на разделение этой сортировки равны log n. Однако часть нашей стратегии слияния или завоевания стоит немного дороже. Слияние будет стоить n за каждый уровень подразделения в дополнение к журналу n, который мы тратим на разделение. Таким образом, часть слияния будет стоить n log n, к сожалению, больше, чем log n. Big O основан на наихудшем случае, поэтому наша сортировка слияния Big O фактически будет O (n log n).

Думая о нашей общей стратегии, у нас есть 2 шага. Первый шаг - разделить массив на более мелкие массивы, пока они не станут одним элементом (т. Е. Уже отсортированными), а затем нам нужно объединить их со смежными списками до тех пор, пока не будет сформирован окончательный отсортированный массив.

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

Если мы запустим приведенный выше код в терминале, вводящем массив [7, 9, 8, 12, 11, 10], мы получим [7, 9, 8] и [12, 11, 10]. Разделенные массивы не упорядочены, но это не имеет значения, потому что мы собираемся продолжать разбиение на все, что у нас есть, это массивы из отдельных элементов. Но пока мы знаем нашу разделяющую часть работ Divide & Conquer. Прежде чем мы погрузимся в рекурсию, давайте сделаем крюк и поработаем над частью завоевания.

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

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

И вот оно! Функционирующая сортировка слиянием. Это отличный способ упорядочить массивы. Как я упоминал ранее, вставка и выборка выполняются значительно быстрее. Быстрая сортировка в среднем сопоставима, но в худшем случае все равно O (n ²), так что давайте откажемся от сортировки слиянием!

Первоначально опубликовано на http://www.aallegranzi.com.