Сортировка слиянием (Merge Sort)

Merge Sort (сортировка слиянием) — это алгоритм сортировки, который использует метод «разделяй и властвуй». Он делит массив на более мелкие подмассивы, сортирует каждый из них и затем объединяет их обратно в один отсортированный массив. Это один из самых эффективных алгоритмов сортировки, особенно для больших массивов.

▎Основные этапы работы Merge Sort:

1. Разделение:

• Если массив содержит один или ноль элементов, он уже отсортирован, и алгоритм завершает свою работу для этого подмассива.

• В противном случае массив разбивается на две половины. Этот процесс продолжается рекурсивно до тех пор, пока все подмассивы не станут размером 1.

2. Слияние:

• После того как все подмассивы были разделены, начинается процесс слияния. Два отсортированных подмассива объединяются в один отсортированный массив.

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

▎Временная сложность:

• Лучший случай: O(n*log(n))

• Средний случай: O(n*log(n))

• Худший случай: O(n*log(n))

▎Пространственная сложность:

• O(n) — требуется дополнительная память для хранения временных массивов во время слияния.

▎Устойчивость:

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

Реализация сортировки на языке программирования C++:

Реализация алгоритма на Python: