Джулиан Бакнелл - Фундаментальные алгоритмы и структуры данных в Delphi

Вывод функции быстродействия сортировки слиянием достаточно сложен. Для простоты ее определения лучше принять, что в исходном списке находится 2(^х^) элементов. Предположим, что элементов 32. На первом уровне рекурсии процедура MSS будет вызываться один раз и на этапе слияния будет не более 32 сравнений. На втором уровне рекурсии процедура MSS будет вызываться два раза, причем количество сравнений при каждом вызове не будет превышать 16. Далее рассматриваем третий, четвертый и, наконец, пятый уровень рекурсии (когда будет выполняться сортировка всего двух элементов), на котором будет иметь место 16 вызовов процедуры по два сравнения в каждом. Таким образом, общее количество сравнений будет равно 5 * 32. Но причиной, по которой было получено пять уровней рекурсии, является то, что мы постоянно на каждом уровне постепенно делили список на две равные половины, а 2(^5^) = 32, что, естественно означает, что log(_2_)32 = 5. Следовательно, не утруждая себя переходом от рассмотренного нами частного случая к общему, можно сказать, что сортировка слиянием принадлежит к классу O(n log(n)) алгоритмов.

Что касается устойчивости, то поскольку элементы перемещаются только при выполнении процедуры слияния, устойчивость всей сортировки слиянием будет зависеть от устойчивости самого слияния двух половин списка. Обратите внимание, что если в обеих половинах имеются элементы с одинаковым значением, то оператор сравнения гарантирует, что первым в результирующий список попадет элемент из первой половины списка. Это означает, что операция слияния сохраняет относительный порядок элементов, и, следовательно, сортировка слиянием будет устойчивой.

Если отслеживать вызовы процедуры MSS в отладчике, то можно обратить внимание, что для небольших интервалов она вызывается очень часто. Например, если в списке содержится 32 элемента, то для списка из 32 элементов процедура MSS будет вызвана один раз, для списка из 16 элементов - дважды, четыре раза для 8 элементов, восемь раз для 4 элементов и шестнадцать раз для 2 элементов (список минимальной длины), т.е. всего 31 раз. Это очень много, особенно если учитывать, что большая часть вызовов (29) приходится для списков длиной восемь и менее элементов. Если бы исходный список содержал 1024 элемента, процедура MSS была бы вызвана 1023 раза, из которых 896 вызовов приходилось бы на долю списков длиной восемь и менее элементов. Просто ужасно! Фактически, для сортировки коротких списков было бы эффективнее использовать нерекурсивный алгоритм. Это позволило бы повысить скорость всей сортировки. Кроме того, применение более простой процедуры дало бы возможность для коротких диапазонов исключить копирование элементов между основным и вспомогательным списком. И одним из лучших методов для ускорения сортировки слиянием является сортировка методом вставок.

Листинг 5.13. Оптимизированная сортировка слиянием

const

MSCutOff = 16;

procedure MSInsertionSort(aList : TList;

aFirst : integer; aLast : integer;

aCompare : TtdCompareFunc);

var

i, j : integer;

IndexOfMin : integer;

Temp : pointer;

begin

{найти наименьший элемент в списке}

IndexOfMin := aFirst;

for i := succ(aFirst) to aLast do

if (aCompare(aList.List^[i], aList.List^[IndexOfMin]) < 0) then

IndexOfMin := i;

if (aFirst <> indexOfMin) then begin

Temp := aList.List^[aFirst];

aList.List^[aFirst] := aList.List^[IndexOfMin];

aList.List^[IndexOfMin] := Temp;

end;

{выполнить сортировку методом вставок}

for i := aFirst+2 to aLast do

begin

Temp := aList.List^[i];

j := i;

while (aCompare(Temp, aList.List^[j-1]) < 0) do

begin

aList.List^[j] := aList.List^[j-1];

dec(j);

end;

aList.List^[j] := Temp;

end;

end;

procedure MS(aList : TList; aFirst : integer; aLast : integer;

aCompare : TtdCompareFunc;

aTempList : PPointerList);

var

Mid : integer;

is j : integer;

ToInx : integer;

FirstCount : integer;

begin

{вычислить среднюю точку}

Mid := (aFirst + aLast) div 2;

{выполнить сортировку первой половины списка с помощью сортировки слиянием или если количество элементов достаточно мало, при помощи сортировки методом вставок}

if (aFirst < Mid) then

if (Mid-aFirst) <= MSCutOff then

MSInsertionSort(aList, aFirst, Mid, aCompare) else

MS (aList, aFirst, Mid, aCompare, aTempList);

{аналогично выполнить сортировку второй половины}

if (suce(Mid) < aLast) then

if (aLast-succ(Mid) ) <= MSCutOf f then

MSInsertionSort(aList, succ(Mid), aLast, aCompare)

else

MS (aList, suce(Mid), aLast, aCompare, aTempList);

{скопировать первую половину списка во вспомогательный список}

FirstCount := suce (Mid - aFirst);

Move(aList.List^[aFirst], aTempList^[0], FirstCount*sizeof(pointer));

{установить значения индексов: i - индекс для вспомогательного списка (т.е. первой половины списка), j - индекс для второй половины списка, ToInx -индекс в результирующем списке, куда будут копироваться отсортированные элементы}