Сравниваем два элемента, на которые указывают два родительских узла. Если меньший элемент находится в первом узле, он находится на своем месте, поэтому переходим к следующему узлу. При этом первый узел будет новым родительским узлом. Если же меньший элемент находится во втором списке, его необходимо удалить из списка и вставить после родительского узла первого списка, а затем перейти к следующему узлу. При этом вновь вставленный узел будет новым родительским узлом. Далее описанный процесс продолжается вплоть до исчерпания улов одного из списков. Если пройден весть первый список, в него добавляются оставшиеся элементы из второго.
Все кажется простым. Тем не менее, может показаться, что в процессе сортировки нам приходится разделять исходный список на большое количество списков, содержащих всего один реальный и один фиктивный узел, а затем объединять их в один список. К счастью, это не так, поскольку в качестве фиктивных начальных узлов можно временно использовать другие узлы из списка и даже не разбивать исходный список на подсписки. Давайте рассмотрим, как это сделать.
Во-первых, потребуется написать метод-драйвер сортировки слиянием. Он будет просто вызывать рекурсивный метод, который и будет заниматься собственно сортировкой. Методу-драйверу будут передаваться два параметра: узел, с которого начинается сортируемый список, и количество элементов в списке. Мы не будем использовать nil в качестве сигнализатора окончания списка - для этого будет применяться счетчик узлов. Реализация простого метода-драйвера приведена в листинге 5.19.
Листинг 5.19. Метод-драйвер для сортировки слиянием односвязных списков
procedure TtdSingleLinkList.Sort(aCompare : TtdCompareFunc);
begin
{если в списке более одного элемента, выполнить сортировку слиянием}
if (Count > 1) then
sllMergesort(aCompare, FHead, Count);
MoveBeforeFirst;
FIsSorted := true;
end;
Как видите, для выполнения сортировки метод-драйвер вызывает функцию sllMergeSort. Эта функция сначала вызывает сама себя для первой, а затем - для второй половины списка, после чего обе половины объединяются в один список. Для обеспечения слияния функция sllMergeSort возвращает последний отсортированный узел.
Листинг 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;
