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

Сколько же памяти потребуется? Только что мы решили, что в худшем случае будет использоваться список, размер которого равен размеру исходного списка, но за счет небольшой хитрости можно снизить требования по дополнительной памяти до половины размера исходного списка.

Представьте себе, что мы находимся на самом верхнем уровне рекурсивного алгоритма. Только что мы выполнили сортировку двух половин исходного списка (будем считать, что первый отсортированный подсписок находится в первой половине списка, а второй - во второй половине), а теперь переходим к их слиянию. Вместо того чтобы выполнить слияние во вспомогательный список, равный по размеру исходному, скопируем первую половину списка в другой список, размер которого равен только половине исходного. Теперь у нас есть вспомогательный список, заполненный элементами из первой половины исходного списка, и исходный список, первая половина которого считается пустой, а вторая заполнена вторым подсписком элементов. При слиянии мы не перезапишем ни один из элементов второго подсписка, поскольку точно известно, что все содержимое вспомогательного списка может поместиться в свободную половину исходного списка.

Листинг 5.12. Стандартная сортировка слиянием

procedure MSS(aList : TList;

aFirst : integer;

aLast : integer;

aCoropare : TtdCompareFunc;

aTempList : PPointerList);

var

Mid : integer;

i, j : integer;

ToInx : integer;

FirstCount : integer;

begin

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

Mid := (aFirst + aLast) div 2;

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

if (aFirst < Mid) then

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

if (suce(Mid) < aLast) then

MSS(aList, succ(Mid), aLast, aCompare, aTempList);

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

FirstCount := suce(Mid - aFirst);

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

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

i := 0;

j := suce (Mid);

ToInx := aFirst;

{выполнить слияние двух списков}

{повторять до тех пор, пока один из списков не опустеет}

while (i < FirstCount) and (j <= aLast) do

begin

{определить элемент с наименьшим значением из следующих элементов в обоих списках и скопировать его; увеличить значение соответствующего индекса}

if (aCompare(aTempList^[i], aList.List^[j]) <= 0) then begin

aList.List^[ToInx] := aTempList^[i];

inc( i );

end

else begin

aList.List^[ToInx] := aList.List^[j];

inc(j);

end;

{в объединенном списке есть еще один элемент}

inc(ToInx);

end;

{если в первом списке остались элементы, скопировать их}

if (i < FirstCount) then

Move(aTempList^[i], aList.List^[ToInx], (FirstCount - i) * sizeof(pointer));

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

end;

procedure TDMergeSortStd(aList : TList;

aFirst : integer;

aLast : integer;

aCompare : TtdCompareFunc);

var

TempList : PPointerList;

ItemCount: integer;

begin

TDValidateListRange(aList, aFirst, aLast, 'TDMergeSortStd');

{если есть хотя бы два элемента для сортировки}

if (aFirst < aLast) then begin

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

ItemCount := suce(aLast - aFirst);

GetMem(TempList, (suce(ItemCount) div 2) * sizeof(pointer));

try

MSS(aList, aFirst, aLast, aCompare, TempList);

finally

FreeMem(TempList, (suce(ItemCount) div 2) * sizeof(pointer));

end;

end;

end;

Если вы внимательно изучите код, приведенный в листинге 5.12, то обнаружите, что он содержит процедуру-драйвер, TDMergeSortStd, которая вызывается для выполнения сортировки списка, и отдельную вспомогательную процедуру, MSS, выполняющую рекурсивную сортировку. Прежде всего, процедура TDMergeSortStd проверяет попадание индекса в допустимые пределы и сам список, а затем - присутствуют ли в списке хотя бы два элемента, которые можно сортировать. После этого создается вспомогательный список указателей с размером, достаточным для хранения половины количества элементов исходного массива. Далее вызывается рекурсивная процедура MSS.

Процедура MSS рекурсивно вызывает сама себя для сортировки первой и второй половин переданной ей части массива. Затем она копирует первую половину во вспомогательный массив. Начиная с этого момента, код представляет собой стандартную реализацию сортировки слиянием, копируя две половины списка в исходный список. Если после выполнения цикла сравнения и копирования во вспомогательном массиве остались элементы, процедура MSS их просто копирует. Если же элементы остались во второй половине списка, их можно не копировать, как и в стандартной реализации метода слияния: они уже находятся на своих местах.