Сортировка объединением

Пользуясь двумя блоками лент по десять лент в каждом, можно переписывать результаты поразрядной упорядоченности, поочередно с одного блока на другой. Время на такую сортировку по числовому ключу выражается так. Этим термином назван метод сортировки с использованием только оперативного накопителя, предложенный Гольдштейном и фон Нейманом. Метод заключается в объединении двух или более упорядоченных массивов информации в одну упорядоченную последовательность (обычно называемую цепочкой). Рассмотрим пример такого объединения.

Гольдштейном и фон Нейманом подробно рассмотрен этот вопрос для случая, когда вся информация помещается в основном запоминающем устройстве. Здесь элемент информации состоит из ключа, занимающего одну ячейку памяти, за которым следует других слов (есть порядок элемента). В таком случае цепочка содержит слов. На блок-схеме показано объединение цепочки в одну упорядоченную цепочку, где есть один из элементов, расположенных таким образом, что они составляют последовательность по возрастающим значениям ключей.
В общем случае объединение двух цепочек с двух магнитных лент в третью цепочку на третьей ленте потребует введения в блок-схему блоков обращения к внешней памяти. Теперь можно рассмотреть процесс упорядочения произвольной последовательности, состоящей из элементов методом последовательного объединения. Этот процесс может быть выполнен следующим образом:
1. Объединяются пары элементов, элементы этих пар рассматриваются как цепочки из одного элемента; формируются цепочки из двух элементов.
2. Пары цепочек элементов последовательности объединяются по описанному выше методу с образованием результирующей цепочки, состоящей из 2+1 элементов.
3. Процесс заканчивается, когда остается только одна цепочка.

Источник: delete-it