Алгоритмы сортировки слиянием, как правило, имеют порядок O(N*log2(N)), но отличаются от других алгоритмов большей сложностью и требуют большого числа пересылок. Алгоритмы слияния применяются в основном, как составная часть внеш- ней сортировки, которая более подробно будет рассматриваться нами во втором томе нашего пособия. Здесь же для понимания принципа слияния мы приводим простейший алгоритм слияния в оперативной памяти.
Сортировка попарным слиянием.
Входное множество рассматривается, как последовательность подмножеств, каждое из которых состоит из единственного элемента и, следовательно, является уже упорядоченным. На первом проходе каждые два соседних одно-элементных множества сливаются в одно двух-элементное упорядоченное множество. На втором проходе двух-элементные множества сливаются в 4-элементные упорядоченные множества и т.д. В конце концов мы получаем одно большое упорядоченное множество.
Важнейшей частью алгоритма является слияние двух упорядоченных множеств. Эту часть алгоритма мы опишем строго.
Программный пример 3.17 иллюстрирует сортировку попарным слиянием в ее обменном варианте - выходные множества формируются на месте входных.
{===== Программный пример 3.17 =====} { Сортировка слиянием } Procedure Sort(var a :Seq); Var i0,j0,i,j,si,sj,k,ke,t,m : integer; begin si:=1; { начальный размер одного множества } while si < N do begin { цикл пока одно множество не составит весь массив } i0:=1; { нач.