Finally
Try
Begin
Begin
Var
Begin
Else
End
Begin
Begin
Begin
Var
Begin
Else
End
Begin
Begin
Begin
Begin
Begin
Var
Begin
repeat Dec(R);
until aCompare(aList.List[R], M) <= 0;
repeat Inc(L);
until aCompare(aList.List[L], M) >= 0;
if L >= R then Break;
Temp:=aList.List[L];
aList.List[L]:=aList.List[R];
aList.List[R]:=Temp;
end;
if aFirst < R then
QuickHoarMDNSort(aList, aFirst, R, aCompare);
aFirst:=R+1;
end;
end;
{ Быстрая сортировка Хоара без рекурсии }
procedure QuickHoarNonRecursiveSort;
L, R, SP: Integer;
M, Temp: Pointer;
Stack: array [0..63] of Integer;
{ Инициализировать стек }
Stack[0]:=aFirst;
Stack[1]:=aLast;
SP:=2;
while SP <> 0 do
{ Извлечь верхний список }
Dec(SP, 2);
aFirst:=Stack[SP];
aLast:=Stack[SP+1];
{ Пока в списке есть хотя бы два элемента }
while aFirst < aLast do
{ В качестве базового выбирается средний элемент }
M:=aList.List[(aFirst+aLast) div 2];
{ Задать начальные значения индексов и приступить к разбиению списка }
L:=aFirst-1; R:=aLast+1;
while True do
repeat Dec(R);
until aCompare(aList.List[R], M) <= 0;
repeat Inc(L);
until aCompare(aList.List[L], M) >= 0;
if L >= R then Break;
Temp:=aList.List[L];
aList.List[L]:=aList.List[R];
aList.List[R]:=Temp;
end;
{ Поместить большой список в стек и
повторить цикл для меньшего подсписка }
if (R - aFirst) < (aLast - R) then
Stack[SP]:=R+1;
Stack[SP+1]:=aLast;
Inc(SP, 2);
aLast:=R;
Stack[SP]:=aFirst;
Stack[SP+1]:=R;
Inc(SP, 2);
aFirst:=R+1;
end;
end;
end;
end;
{ Сортировка слиянием }
procedure MSS;
Mid, i, j, ToInx,
FirstCount: Integer;
{ Вычислить среднюю точку }
Mid:=(aFirst + aLast) div 2;
{ Рекурсивная сортировка слиянием первой и второй половин списка }
if aFirst < Mid then
MSS(aList, aFirst, Mid, aCompare, aTempList);
if (Mid+1) < aLast then
MSS(aList, Mid+1, aLast, aCompare, aTempList);
{ Скопировать первую половину списка во вспомогательный список }
FirstCount:=Mid-aFirst+1;
Move(aList.List[aFirst], aTempList[0], FirstCount*SizeOf(Pointer));
{ Установить значения индексов: i - индекс для вспомогательного списка
(т.е. первой половины); j - индекс для второй половины списка;
ToInx - индекс в результирующем списке, куда будут копироваться
отсортированные элементы }
i:=0; j:=Mid+1; ToInx:=aFirst;
{ Выполнить слияние двух списков; повторять
пока один из списков не опустеет }
while (i < FirstCount) and (j <= aLast) do
{ Определить элемент с наименьшим значением из следующих
элементов в обоих списках и скопировать его; увеличить
значение соответствующего индекса }
if aCompare(aTempList[i], aList.List[j]) <= 0 then
aList.List[ToInx]:=aTempList[i];
Inc(i);
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 MergeSortStd(aList: TList;
aFirst, aLast: Integer; aCompare: TCompareFunc);
TempList: PPointerList;
ItemCount: Integer;
{ Есть хотя бы два элемента для сортировки }
if aFirst < aLast then
{ создать временный список указателей }
ItemCount:=aLast-aFirst+1;
GetMem(TempList, ((ItemCount+1) div 2)*SizeOf(Pointer));
MSS(aList, aFirst, aLast, aCompare, TempList);
FreeMem(TempList, ((ItemCount+1) div 2)*SizeOf(Pointer));
end;
end;
end;