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

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

Разновидностью сортировки вставкой является метод вон Неймана, который заключался в следующем: сначала анализируются 1-ые элементы обоих массивов, подлежащих сортировке. В новый 3-й массив после каждого сравнения попадает меньший элемент. Процесс продолжается до исчерпания элементов одного из массивов. Затем остаток другого массива дописывается в новый.

Пусть имеются 2 отсортированных в порядке возрастания массива:

p[1], p[2],…p[n]

q[1], q[2],… q[n]

Пустой массив r[1], r[2],…r[n], который необходимо заполнить значениями массивов p и q в порядке возрастания.

Для слияния выполняют следующие действия: сравнивают p[1] с q[1] и меньшее записывают в r[1]

3

5

7

44

6

8

33

255

1) 3 и 6 2) 5 и 6 3) 7 и 6 4) 7 и 8

3

5

6

7