Сортировка слиянием с рекурсией.

Слиянием двух упорядоченных множеств называется процесс упорядочения объединения данных множеств.

Теорема. Пусть даны два упорядоченных множества {A₁,…,A_{N }} и {B₁,…,B_N }.       В рамках алгоритмов, основанных на простых сравнениях, данные множества нельзя слить быстрее, чем за 2N-1 сравнение в худшем случае. Т.е. 2N-1 является нижней оценкой времени работы алгоритма, если учитывать только время, расходуемой на сравнения элементов множеств, и если положить время одного сравнения равным 1.

Доказательство. Пусть для конкретных заданных множеств выполняются соотношения A_i< B_i и A_i+1> B_i. Тогда отсортированное объединение множеств выглядит следующим образом: {A₁, B₁, A₂, B₂ ,…, A_N,B_{N }}.  Если хотя бы одно из приведенных 2N-1 соотношений не будет проверено, то найдется еще хотя бы одна перестановка элементов множества, удовлетворяющая всем приведенным соотношениям. Например, если не будет проверено соотношение A₂> B₁, то следующая последовательность будет удовлетворять всем остальным соотношениям:

{A₁, A₂, B₁, B₂ ,…, A_N,B_{N }}.

Более того, отношения между всеми остальными элементами останутся неизменными. Т.о. мы доказали необходимость всех приведенных сравнений для правильного упорядочивания указанных данных, из чего непосредственно вытекает требуемое.

¢

Дословно так же доказывается следующая теорема

Теорема. Пусть даны два упорядоченных множества {A₁,…,A_N +1} и {B₁,…,B_{N }}.       В рамках алгоритмов, основанных на простых сравнениях, данные множества нельзя слить быстрее, чем за 2N сравнений элементов множества в худшем случае.

Алгоритм слияния. Пусть даны два упорядоченных множества {A₁,…,A_M} и {B₁,…,B_{N }}. Введем индексы i, j и k . Изначально i=1, j=1 и k=1 .

Пока  i£M и j£N:

     Если A_i < B_j то

       С_k++ = A_i++

иначе

      С_k++ = B_i++

Конец Если

Конец Цикла

Пока  I £ M:

       С_k++ = A_i++

Конец Цикла

Пока  j £ N:

      С_k++ = B_i++

Конец Цикла

Легко увидеть,  что в данном алгоритме элементы множества сравниваются не более M+N-1 раз. Т.о. данный алгоритм оказывается строго оптимальным по числу сравнений элементов сортируемого множества (по крайней мере в алгоритмах, основанных на простых сравнениях).

Вопрос на понимание: можно ли два упорядоченных множества {A₁,…,A_{N }} и {B₁,…,B_N} слить быстрее чем за 2N-1 операций сравнения в каком либо алгоритме, основанном операциях сравнения? … на операциях простого сравнения?

Алгоритм сортировки слиянием. Обозначим данный алгоритм Z(A₁,…,A_{M )}, где {A₁,…,A_N } – сортируемое множество элементов. Алгоритм имеет следующий вид

Если число обрабатываемых элементов £ 1 то ВЫЙТИ

M₁ = [ M/2 ]; M₂ = M-M₁; // размеры половин массива

Z(A₁,…,A_M1 )

Z(A_M1+1,…,A_M )

Слить упорядоченные множества {A₁,…,A _{M1 }} и { A_M1+1,…,A_M } в массив B.

Скопировать массив B в массив {A₁,…,A_{N }}.

Легко видеть, что данный алгоритм решает задачу за время O(N log₂ N), где N – количество элементов в сортируемом массиве.

Недостатком алгоритма является необходимость использования дополнительного массива с размером, равным  размеру исходного массива.

Сортировка слиянием без рекурсии.

Предыдущий алгоритм можно модифицировать так, что он уже не будет использовать рекурсию. Действительно. Рассмотрим последовательно все пары элементов в сортируемом массиве. Каждый из элементов в паре представляет собой уже отсортированный массив длины 1, поэтому эти массивы (пока длины 1) можно слить в упорядоченные куски длины 2. Далее мы рассматриваем уже пары упорядоченных массивов длины 2 и сливаем их в массивы длины 4. И т.д.

Отметим, что при этих операциях на k-том проходе по упорядочиваемому массиву на правом конце массива мы будем получать либо ситуацию, когда у правого оставшегося куска (длины £ 2^k ) вообще нет парного куска для слияния, либо кусок есть и его длина £ 2^k. В первом случае делать вообще ничего не нужно, а во втором следует стандартным способом сливать куски, возможно, существенно различной длины.

Легко видеть, что данный алгоритм решает задачу за время O(N log₂ N), где N – количество элементов в сортируемом массиве.