Это необходимо, если в массиве А могут встречаться одинаковые значения,

претендующие на одно и то же место в В }

while B[k]<>Pr do

inc(k);

B[k]:=A[i]; { записываем A[i] на найденное место в массив В}

end;

Сортировка слиянием.

Этот метод предполагает, что имеется два или несколько наборов данных, каждый из которых уже упорядочен. Нужно объединить их в один упорядоченный набор данных. Как входные, так и выходной наборы могут размещаться во внешней памяти (в файлах). Алгоритм заключается в том, что заводится столько указателей, сколько входных наборов данных объединяется одновременно; каждый указатель сначала указывает на первый элемент в каждом наборе. Выбирается самый маленький элемент из тех, на которые указывают эти указатели, и он переписывается в выходной массив, после чего указатель набора, из которого был переписан элемент, увеличивается на единицу (и теперь указывает на второй элемент этого набора). Далее снова производится выбор наименьшего элемента из тех, на которые указывают указатели, и так пока не будут выбраны все элементы из всех наборов. Если кончается один из наборов, а их всего два, то оставшиеся элементы второго набора дописываются в конец выводного файла.

Если сливаются одновременно более двух наборов, вычерпанный набор перестает рассматриваться при выборе минимального элемента, или в этом наборе искусственно создается дополнительный элемент с очень большим ключом (каких не может быть у реальных элементов) и при выборе он никогда не будет взят. При этом не меняется схема выбора. Если первоначально было N упорядоченных коротких наборов данных, то объединяя их попарно этим методом, после первого прохода станет N/2 упорядоченных наборов, но каждый из них будет уже в два раза длиннее. Повторяя этот процесс и беря каждый раз выходные наборы в качестве входных для слияния, можно в итоге получить один упорядоченный набор. Первоначальные N наборов можно получить из исходного, например, беря по паре элементов, поменяв их местами, если они не в правильном порядке.

Строки