Листинг 5.11. Слияние двух отсортированных массивов TList
procedure TDListMerge( aList 1, aList2, aTarget List : TList;
aCompare : TtdCompareFunc);
var
Inx1, Inx2, Inx3 : integer;
begin
{подготовить результирующий список}
aTargetList.Clear;
aTargetList.Capacity := aList1.Count + aList2.Count;
{инициализировать счетчики}
Inx1 := 0;
Inx2 := 0;
Inx3 := 0;
{выполнять цикл до исчерпания элементов одного из списка...}
while (Inx1 < aList1.Count) and (Inx2 < aList2.Count) do
begin
{определить наименьшее значение из двух списков и скопировать его в результирующий список; увеличить значения индексов на единицу}
if aCompare (aList1.List^[Inx1], aList2.List^[Inx]) < = 0 then begin
aTargetList.List^[Inx3] := aList1.List^[Inx1];
inc(Inx1);
end
else begin
aTargetList.List^[Inx3] := aList2.List^[Inx2];
inc(Inx2);
end;
inc(Inx3);
end;
{выполнение цикла прекращается при исчерпании элементов одного из списков; если в первом списке еще остались элементы, скопировать их в результирующий список}
if (Inx1 < aList1.Count) then
Move(aList1.List^[Inx1], aTargetList.List^[Inx3],
(aList1.Count - Inx1) * sizeof(pointer)) {в противном случае скопировать все элементы, оставшиеся во втором списке, в результирующий список}
else
Move(aList2.List^[Inx2], aTargetList.List^[Inx3], (aList2.Count - Inx2) * sizeof(pointer));
end;
Обратите внимание, что в коде копирование оставшихся элементов в одном или другом списке выполняется с помощью процедуры Move. Для копирования можно было бы организовать небольшой цикл, однако процедура Move работает намного быстрее.
Время выполнения алгоритма двухпутевого слияния зависит от количества элементов в обоих исходных списках. Если в первом из них находится n элементов, а во втором - m, нетрудно прийти к выводу, что в худшем случае будет произведено (n + m) сравнений. Следовательно, алгоритм двухпутевого слияния принадлежит к классу O(n).
Каким же образом алгоритм двухпутевого слияния помогает выполнить сортировку? Для его работы необходимо иметь два отсортированных списка меньшей длины, из которых создается один больший список. На основе такого описания можно прийти к рекурсивному определению сортировки слиянием: разделите исходный список на две половины, примените к каждой половине алгоритм сортировки слиянием, а затем с помощью алгоритма слияния объедините подсписки в один отсортированный список. Рекурсия заканчивается, когда под-под-подсписок, переданный алгоритму сортировки, содержит всего один элемент, поскольку он, очевидно, является отсортированным.
Сортировка слиянием обладает только одним недостатком - алгоритм слияния требует наличия третьего списка, в котором будут храниться результаты слияния.
В отличие от всех ранее рассмотренных методов сортировки, которые сортируют элементы непосредственно в самом исходном списке, сортировка слиянием для работы требует большого дополнительного объема памяти. В качестве первого приближения в самой простой реализации может показаться, что для выполнения сортировки понадобиться новый вспомогательный список, размер которого равен сумме размеров двух исходных списков. Элементы из обоих списков будут помещаться во вспомогательный список, а затем после слияния - в основной список. Несмотря на то что можно разработать алгоритм, который выполняет операцию слияния, не требуя вспомогательного списка, на практике его выполнение занимает намного больше времени. Поэтому при необходимости применения сортировки слиянием нужно смириться с дополнительными требованиями в отношении памяти.
Сколько же памяти потребуется? Только что мы решили, что в худшем случае будет использоваться список, размер которого равен размеру исходного списка, но за счет небольшой хитрости можно снизить требования по дополнительной памяти до половины размера исходного списка.
Представьте себе, что мы находимся на самом верхнем уровне рекурсивного алгоритма. Только что мы выполнили сортировку двух половин исходного списка (будем считать, что первый отсортированный подсписок находится в первой половине списка, а второй - во второй половине), а теперь переходим к их слиянию. Вместо того чтобы выполнить слияние во вспомогательный список, равный по размеру исходному, скопируем первую половину списка в другой список, размер которого равен только половине исходного. Теперь у нас есть вспомогательный список, заполненный элементами из первой половины исходного списка, и исходный список, первая половина которого считается пустой, а вторая заполнена вторым подсписком элементов. При слиянии мы не перезапишем ни один из элементов второго подсписка, поскольку точно известно, что все содержимое вспомогательного списка может поместиться в свободную половину исходного списка.
Листинг 5.12. Стандартная сортировка слиянием
procedure MSS(aList : TList;
aFirst : integer;
aLast : integer;
aCoropare : TtdCompareFunc;
aTempList : PPointerList);
var
Mid : integer;