Зарождение компьютеров, активное развитие точных наук, появление дисциплин на стыке направлений потребовали создания принципов работы с данными, в том числе способов упорядочивания. Основатель «Школы траблшутеров» Олег Брагинский и ученик Владислав Иванов изучают один из базовых методов группировки.
Отец современных вычислительных машин, внёсший вклад в физику, математику, информатику, экономику и теорию игр, Джон фон Нейман в 1945 году создаёт сортировку слиянием (Merge Sort) – одну из самых стабильных и быстрых в мире алгоритмов.
Идея заключается в постепенном делении массива на равные доли, пока внутри не окажется по одному значению: срабатывает рекурсия – процедура воспроизводит собственные шаги. Затем полученные фрагменты сравниваются и соединяются вновь.
Рассмотрим пример: последовательность из шести элементов [7, 6, 3, 4, 8, 1] требуется выстроить по возрастанию.
Разбиваем набор пополам – выходят подмассивы [7, 6, 3] и [4, 8, 1].
Неделимых частиц пока нет – дробим дальше:
Появляются одиночки [7] и [1], но связки [6, 3] и [4, 8] ещё предстоит расцепить. На нижней ступени образуются четыре ячейки: [6] и [3], [4] и [8].
Первая цель достигнута – массив рассыпан до атомов. Двигаемся в обратную сторону, сравнивая пары: [6] больше [3], поэтому меньшее число выдвигаем вперёд. [4] и [8] проверяем аналогично – порядок сохраняется.
Возвращаемся на предыдущий уровень, где присутствуют дуэты [7] и [3, 6], [4, 8] и [1]. Сопоставляем звенья: [7] больше, чем [3], значит, тройка возглавляет обновлённый ряд. Шестёрка тоже уступает семёрке и встаёт следом. Подобное проделываем со вторым тандемом.
Остаётся собрать общую цепочку. К сличению предлагаются части [3, 6, 7] и [1, 4, 8]: партию открывают [3] и [1], после отправления единицы в «головной вагон» сверяем [3] и [4]. Далее [4] и [6], затем [6] и [7], в конце [7] и [8]. Слияние завершено – получаем [1, 3, 4, 6, 7, 8].
Скорость метода описывается линейно-логарифмической оценкой:
T = O(n·log n),
где T – время работы, n – число элементов.
Затраты на хранение прямо зависят от количества данных:
Q = O(n),
где Q – требуемый объём.
Детище фон Неймана устойчиво на массивах любой длины, прекрасно подходит для связных списков и внешней сортировки. Недостаток – жажда дополнительной памяти, равной размеру исходного набора. Существуют и улучшения – вплоть до многопоточного слияния.