Сегодня разберем алгоритм, в котором используется несколько интересных приемов программирования. Будет много картинок, куда ж без них. Приятного просмотра! :)
Сортировка слиянием – это рекурсивный алгоритм сортировки, основанный на принципе «разделяй и властвуй».
Принцип «разделяй и властвуй» - это подход к разработке алгоритмов, заключающийся в рекурсивном разбиении решаемой задачи на две или более подзадачи того же типа, но меньшего размера, и комбинировании их решений для получения ответа к исходной задаче. Разбиения выполняются до тех пор, пока все подзадачи не окажутся элементарными. Для нашего случая элементарной задачей будет считаться массив, содержащий один элемент, т.к. такой массив по умолчанию уже отсортирован.
Описание:
Итак, сортировка слияния заключается в разбиении исходного массива на два массива меньшего размера и если полученные массивы не подпадают под элементарную задачу, то каждый из подмассивов продолжает разбиваться до тех пор, пока в них не останется по одному элементу. После начинаем их последовательно сливать в один массив по ходу дела производя сортировку.
Сортировка осуществляется путем сравнения наименьших элементов каждой половины. Первый элемент каждого списка сравнивается с первым. Меньший их первых элементов добавляем в отсортированный список и индекс этой половины сдвигаем вперёд на 1. Затем мы сравниваем второе наименьшее значение одной половины с первым наименьшим значением другой половины и т.д.
Принцип действия:
Пожалуй, стоит нарисовать как это будет выглядеть:
Блок-схема в этот раз будет состоять из двух частей:
Реализация на Python 3:
Алгоритмическая сложность:
Довольно не простой алгоритм и кода намного больше чем до этого и, наверняка, еще и чуть быстрее предыдущего метода. Нафиг он нам такой, да еще и с рекурсией? Разбираемся.
Основная операция в нашем алгоритме - это слияние двух половин. На слияние нам требуется последовательно сравнить элементы каждого из них. На каждом уровне мы совершаем:
Откинув все постоянные величины получаем количество операций на каждом уровне – O(n).
Количество элементов на уровнях равно 8 - 4 - 2, не трудно заметить, что на каждом уровне мы получили количество элементов равное степени двойки: 2³ + 2² + 2¹. Таким образом количество уровней h, т.е. глубина рекурсии, будет примерно равна двоичному логарифму от количества элементов в массиве log₂(8) = 3 ---> О(log(n)).
Итого: О(n) операций повторяем log(n) раз ---> O(n*log(n)).
По памяти нашей реализации требуется только место для хранения рекурсии, а это зависит от её глубины ---> О(log(n)).
Стоит отметить, что сортировка слиянием будет делить и склеивать массив вне зависимости от того, был он отсортирован изначально или нет. Поэтому сортировка слиянием не самое лучшее решение, когда надо отсортировать частично упорядоченный массив.
Так насколько же он быстрее уже изученных алгоритмов?
Настолько, что кажется что он работает с постоянным временем. Выделим отсюда наш график:
Да, тут я добавил еще массив из 10 миллионов чисел (для наглядности). Так вот, скорость нашего алгоритма растет практически линейно (но не забываем о логарифме) с увеличением количества элементов.