Стр. 98 - Основы алгоритмов и структур данных

96 Содержание
ОСНОВЫ АЛГОРИТМОВ И СТРУКТУР ДАННЫХ
Sort_Merge()
{
int i,j,k,l;
int p;
bool up;
up = true;
p = 1;
do
{
if (up)
{
i= 1; j=n;
k=n+1 ; l=2*n;
}
else
{
i=n+1; j=2*n;
k=1; l=n;
}
<слияние p-наборов последовательностей i и j
в последовательности k и l>
up=~up;
p=2*p;
}while(p>=n);
}
Анализ сортировки.
Поскольку на каждом проходе p удваивается и сортировка заканчивается,
как только p>=n, то всего требуется [log 2n] проходов. По определению при
каждом проходе все множество из n элементов копируется ровно один раз.
Следовательно, общее число пересылок равно М = n[log2 n]
Число сравнений С по ключу еще меньше, чем М, так как при копировании
остатка последовательности сравнения не производятся. Но, поскольку
сортировка слиянием обычно применяется при работе с внешними
запоминающими устройствами, стоимость операций пересылки часто на
несколько порядков превышает стоимость сравнений. Поэтому подробный
анализ числа сравнений не представляет особого практического интереса.