Алгоритмы сортировки в танцах [2] Сортировка слиянием как немецкий народный танец

Сортировка слиянием (англ. merge sort) — алгоритм сортировки, который упорядочивает списки (или другие структуры данных, доступ к элементам которых можно получать только последовательно, например — потоки) в определённом порядке. Эта сортировка — хороший пример использования принципа «разделяй и властвуй». Сначала задача разбивается на несколько подзадач меньшего размера. Затем эти задачи решаются с помощью рекурсивного вызова или непосредственно, если их размер достаточно мал. Наконец, их решения комбинируются, и получается решение исходной задачи. Время работы алгоритма порядка O(n*log n) при отсутствии деградации на неудачных случаях, которая является больным местом быстрой сортировки (тоже алгоритм порядка O(n*log n), но только для среднего случая). Исполняется трансильвано-саксонский (немецкий) народный танец. Создано в Sapientia University, Tirgu Mures (Marosvásárhely), Romania. Режиссеры: Kátai Zoltán and Tóth László. Хореограф: Füzesi Albert.