Skip to content

MergeSort (сортировка слиянием)

Данный вид сортировки могут давать на livecode. Суть алгоритма: разделение входного среза на две равные половины с рекурсивной сортировкой.

Визуализация алгоритма:

Сортировка слиянием фактически включает две функции: рекурсивную mergeSort и merge функцию.

Реализуем сортировку на практике.

  1. Расположи файл mergesort.go в папке module3/algo

Сначала напишем функцию mergeSort(). Это рекурсивная функция, то есть она вызывает сама себя. В данном случае она фактически вызывает себя дважды. Смысл mergeSort в том, чтобы разбить массив на две примерно равные части, вызвать себя для этих частей, а затем вызвать merge(), чтобы собрать эти половины вместе.

Функция merge() используется для объединения двух отсортированных списков обратно в один отсортированный список, где действительно происходит «магия». На самом низком уровне рекурсии каждый из двух отсортированных списков будет иметь длину 1. Эти списки с одним элементом будут объединены в отсортированный список длины 2 и далее продолжат объединяться рекурсивно.

  1. Напишем тест и проверим нашу сортировку:

  1. Запустим тест:

Тест прошёл успешно!

Зачем использовать сортировку слиянием?

Плюсы:

  • Быстрота. Сортировка слиянием выполняется намного быстрее, чем пузырьковая, поскольку используется O(n*log(n)) вместо O(n^2).

  • Стабильность. Сортировка слиянием также является стабильной сортировкой. Это означает, что значения с повторяющимися ключами в исходном списке будут в том же порядке, что и в отсортированном списке.

Минусы:

  • Дополнительная память. Большинство алгоритмов сортировки можно выполнить с использованием одной копии исходного массива. Для сортировки слиянием требуется дополнительный массив в памяти для объединения отсортированных подмассивов.

  • Рекурсия. Сортировка слиянием требует многих рекурсивных вызовов функций, а вызовы функций могут потребовать значительных ресурсов.

Если тебе нужен алгоритм сортировки для использования в производственной системе, рекомендуем не изобретать велосипед и использовать встроенный метод sort.Sort .

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

Сортировка слиянием имеет сложность O(n*log(n)). Не дайте себя обмануть, потому что в коде нет явного количества циклов for для подсчета. В случае сортировки слиянием важно количество рекурсивных вызовов функций.

  1. Напишем бэнчмарк и сравним производительность:

  1. Запустим бенчмарк:

Поэкспериментируй с различным количеством элементов: 5000, 10000, 20000.

Рекомендуем также изучить дополнительные материалы по теме: