Листинг 5.20. Рекурсивная сортировка слиянием для односвязных списков

function TtdSingleLinkList.sllMergesort(aCompare : TtdCompareFunc;

aPriorNode : PslNode;

aCount : longint): PslNode;

var

Count2 : longint;

PriorNode2 : PslNode;

begin

{сначала обрабатывается простой случай: если в списке всего один элемент, он отсортирован, поэтому выполнение функции завершается}

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;

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

if (aCount1 = 0) then begin

LastNode^.slnNext := Node2;

for i := 0 to pred(aCount2) do LastNode := LastNode^.slnNext;

end

{если закончились элементы во втором списке, то Node2 будет первым узлом в оставшемся списке; пройти список до последнего узла и связать его с узлом Node2}

else begin

for i := 0 to pred(aCount1) do

LastNode := LastNode^.slnNext;

LastNode^.slnNext := Node2;

end;

{вернуть последний узел}

Result := LastNode;

end;

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

Листинг 5.22. Сортировка слиянием для двухсвязного списка