{сначала обрабатывается простой случай: если в списке всего один элемент, он отсортирован, поэтому выполнение функции завершается}
if (aCount = 1) then begin
Result := aPriorNode^.slnNext;
Exit;
end;
{разбить список на две части}
Count2 := aCount div 2;
aCount := aCount - Count2;
{выполнить сортировку слиянием первой половины: вернуть начальный узел для второй половины}
PriorNode2 := sllMergeSort(aCompare, aPriorNode, aCount);
{выполнить сортировку слиянием второй половины}
sllMergeSort(aCompare, PriorNode2, Count2);
{объединить две половины}
Result := sllMerge(aCompare, aPriorNode, aCount, PriorNode2, Count2);
end;
Метод сортировки слиянием вызывается с указанием начального узла сортируемого списка и количества узлов в списке. Имея такие входные данные, за счет прохождения списка и подсчета узлов можно определить, где начинается вторая половина списка. В качестве возвращаемого параметра после сортировки первой половины списка используется последний узел первой половины, который служит фиктивным начальным узлом для второй половины. В любом случае нам приходится проходить список. Тогда почему бы нам заодно не определить положение средней точки?
И последняя часть реализации сортировки - сама функция слияния. Ее код приведен в листинге 5.21. Она не представляет никаких трудностей для понимания. Начальным узлом объединенного списка будет служить родительский узел первого подсписка. Функция возвращает последний элемент объединенного списка (он будет использоваться в качестве родительского узла для несортированной части подсписка).
Листинг 5.21. Фаза слияния при сортировке слиянием односвязного списка
function TtdSingleLinkList.sllMerge( aCompare : TtdCompareFunc;
aPriorNode1 : PslNode; aCount1 : longint;
aPriorNode2 : PslNode; aCount2 : longint): PslNode;
var
i : integer;
Node1 : PslNode;
Node2 : PslNode;
LastNode : PslNode;
Temp : PslNode;
begin
LastNode := aPriorNode1;
{извлечь первые два узла}
Node1 := aPriorNode1^.slnNext;
Node2 := aPriorNode2^.slnNext;
{повторять цикл до исчерпания элементов одного из списков}
while (aCount1 <> 0) and (aCount2<> 0) do
begin
if (aCompare(Node1^.slnData, Node2^.slnData) <= 0) then begin
LastNode := Node1;
Node1 := Node1^.slnNext;
dec(aCount1);
end
else begin
Temp := Node2^.slnNext;
Node2^.slnNext := Node1;
LastNode^.slnNext := Node2;
LastNode := Node2;
Node2 := Temp;
dec(aCount2);
end;
end;