3.3 Сортировка

Слияние означает объединение двух или более упорядоченных массивов в один упорядоченный массив. Можно, например, слить подмассивы 503 703 765 и 087 512 677 и получить 087 503 512 677 703 765. Простой способ сделать это - сравнить два наименьших элемента, вывести наименьший из них и повторить эту процедуру. Начав с

и т. д. Необходимо решить, что делать в случае, когда исчерпается один из массивов. Весь процесс подробно описан в следующем алгоритме.

Алгоритм М (Двухпутевое слияние). Этот алгоритм осуществляет слияние упорядоченных массивов x₁ х₂ … х_m и y₁ у₂ … у_n в массив z₁ z₂ … z_m+n.

Ml. [Начальная установка.].Установить i l, j l, k l.

М2. [Найти наименьший элемент.] Если x_i y_j, перейти к шагу М3; в противном случае перейти к шагу М5.

М3. [Вывести x_i] Установить z_k x_i, k k + l, i i + l. Если i m, вернуться к шагу М2.

М4. [Передать y_j,...,y_n.] Установить (z_k, …, z_m+n) (y_j,..., y_n) и завершить выполнение алгоритма.

М5. [Вывести y_j.] Установить z_k y_j, k k + 1, j j + 1. Если j n, вернуться к шагу M2.

М6. [Передать x_i,..., х_m.] Установить (z_k,..., z_m+n) (x_i,..., x_m) и завершить выполнение алгоритма.

Рис. 2. Слияние

Эта простая процедура, по существу, - наилучший из возможных способов слияния на компьютере с обычной архитектурой, когда m n. (Но, если m гораздо меньше n, можно разработать более эффективные алгоритмы сортировки, хотя в общем случае они довольно сложны.) Алгоритм М без существенной потери эффективности можно немного упростить, добавив в конец исходных массивов искусственных "стражей" (ограничивающие элементы x_m+1 = y_m+1 = ) и остановившись перед выводом .

Общий объем операций, выполняемых алгоритмом М, по существу, пропорционален m + n, откуда понятно, почему считается, что слияние - более простая задача, чем сортировка. Однако задачу сортировки можно свести к слияниям, сливая все более длинные подмассивы до тех пор, пока не будет рассортирован весь массив. Такой подход можно рассматривать как развитие идеи сортировки методом вставок: вставка нового элемента в упорядоченный массив - частный случай слияния при n = 1. Чтобы ускорить процесс вставок, можно рассмотреть вставку нескольких элементов за один раз, группируя несколько операций, а это естественным образом приведет к общей идее сортировки методом слияния. С исторической точки зрения метод слияний - один из самых первых методов сортировки при помощи компьютеров; он был предложен Джоном фон Нейманом.