ToInx - индекс в результирующем списке, куда будут копироваться

отсортированные элементы }

i:=0; j:=Mid+1; 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 MergeSortStd(aList: TList;

aFirst, aLast: Integer; aCompare: TCompareFunc);

Var

TempList: PPointerList;

ItemCount: Integer;

Begin

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

if aFirst < aLast then

Begin

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

ItemCount:=aLast-aFirst+1;

GetMem(TempList, ((ItemCount+1) div 2)*SizeOf(Pointer));

Try

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

Finally

FreeMem(TempList, ((ItemCount+1) div 2)*SizeOf(Pointer));

end;

end;

end;

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

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

Рис. 4.2. Пример слияния двух массивов.

Контрольные вопросы

1. Перечислите свойства статических структур данных.

2. Приведите примеры объявления и применения вектор и массивов.

3. В чем состоит преимущество их использования открытых массивов?

4. Что такое множества? Описание и применение множеств.

5. Записи упакованные, неупакованные, с вариантами.

6. Опишите алгоритмы линейного и бинарного поиска.

7. Перечислите стратегии сортировки, приведите классификацию алгоритмов сортировки.

8. Опишите алгоритмы сортировки выборкой, пузырьковой, вставками.

9. Опишите разновидности алгоритмов сортировки методом Шелла.

10. Опишите алгоритмы поразрядной цифровой сортировки, методом Хоара и слиянием.