Сортировка слиянием (англ. merge sort) — алгоритм сортировки, который упорядочивает списки (или другие структуры данных, доступ к элементам которых можно получать только последовательно, например — потоки) в определённом порядке. Сначала задача разбивается на несколько подзадач меньшего размера. Затем эти задачи решаются с помощью рекурсивного вызова или непосредственно, если их размер достаточно мал. Наконец, их решения комбинируются, и получается решение исходной задачи. Алгоритм был изобретён Джоном фон Нейманом в 1945 году.
Странно, но мне показалось, что данный алгоритм не так сильно освещён в интернете в целом и на python в частности. А ведь именно этот алгоритм чаще всего применяется для сортировки данных не помещающихся в оперативке, т.е. хранящихся в файлах(внешние сортировки). Как и в случае с быстрой сортировкой Хоара, существует 2 реализации данного алгоритма. Рекурсивная и нет) Скажу по секрету, не рекурсивную реализацию мне предоставил так же мой преподаватель Деон. Более того, она ещё и не требует дополнительной памяти, что в классическом варианте относят к её основным минусам!
Для решения задачи сортировки эти три этапа выглядят так:
- Сортируемый массив разбивается на две части примерно одинакового размера;
- Каждая из получившихся частей сортируется отдельно, например — тем же самым алгоритмом;
- Два упорядоченных массива половинного размера соединяются в один.
Рекурсивное разбиение задачи на меньшие происходит до тех пор, пока размер массива не достигнет единицы (любой массив длины 1 можно считать упорядоченным).
Нетривиальным этапом является соединение двух упорядоченных массивов в один. Основную идею слияния двух отсортированных массивов можно объяснить на следующем примере. Пусть мы имеем две стопки карт, лежащих рубашками вниз так, что в любой момент мы видим верхнюю карту в каждой из этих стопок. Пусть также, карты в каждой из этих стопок идут сверху вниз в неубывающем порядке. Как сделать из этих стопок од