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

Два массива: 5, 8, 23, 65 1, 6, 34, 47

Записываем меньшее значение: 1

5, 8, 23, 65 1, 6, 34, 47

Записываем меньшее значение: 5

5, 8, 23, 65 1, 6, 34, 47

Записываем меньшее значение: 6

5, 8, 23, 65 1, 6, 34, 47

Записываем меньшее значение: 8

5, 8, 23, 65 1, 6, 34, 47

Записываем меньшее значение: 23

5, 8, 23, 65 1, 6, 34, 47

Записываем меньшее значение: 34

5, 8, 23, 65 1, 6, 34, 47

Записываем меньшее значение: 47

Осталось число 65.

Внешняя сортировка прямым слиянием.

Сортировка состоит из последовательности шагов, в каждом из которых выполняется распределение состояния файла A в файлы B и C, а затем слияние файлов B и C в файл A. На первом шаге для распределения последовательно читается файл A, и записи a1, a3,..., a(n-1) пишутся в файл B, а записи a2, a4,..., an - в файл C (начальное распределение). Начальное слияние производится над парами (a1, a2), (a3, a4),..., (a(n-1), an), и результат записывается в файл A. На втором шаге снова последовательно читается файл A, и в файл B записываются последовательные пары с нечетными номерами, а в файл C - с четными. При слиянии образуются и пишутся в файл A упорядоченные четверки записей. И так далее.

Массив: 23, 8, 5, 65, 47, 34, 1, 6

Шаг 1: файл В 23, 5, 47, 1

файл С 8, 65, 34, 6

Файл А: 8, 23, 5, 65, 34, 47, 1, 6

Шаг 2: файл В 8, 23, 34, 47

файл С 5, 65, 1, 6

Файл А: 5, 8, 23, 65, 1, 34, 6, 47

Шаг 3: файл В 5, 8, 23, 65

файл С 1, 34, 6, 47

Файл А: 1, 5, 8, 34, 6, 23, 47, 65

Шаг 4: файл В 1, 5, 8, 34

файл С 6, 23, 47, 65

Файл А: 1, 5, 6, 8, 23, 34, 47, 65

Естественное слияние.

Алгоритм слияния можно использовать и для сортировки массивов, если последовательно применить его несколько раз ко все более длинным упорядоченным последовательностям. Для этого:

1. в исходном наборе выделяются две подряд идущие возрастающие подпоследовательности (серии)

2. эти подпоследовательности (серии) сливаются в одну более длинную упорядоченную последовательность так, как описано выше

3. шаги 1 и 2 повторяются до тех пор, пока не будет достигнут конец входного набора

4. шаги 1 –3 применяются к новому полученному набору, т.е. выделяются пары серий, которые сливаются в еще более длинные наборы, и.т.д. до тех пор, пока не будет получена единая упорядоченная последовательность.

Массив: 24, 08, 13, 17, 06, 19, 20, 11, 07, 55, 33, 22, 18, 02, 40

Этап 1. Выделяем в нем серии (показаны скобками) и попарно сливаем их:

(24), (08, 13, 17), (06, 19, 20), (11), (07, 55), (33), (22), (18), (02, 40)

(24) + (08, 13, 17) = (08, 13, 17, 24)

(06, 19, 20) + (11) = (06, 11, 19, 20)

(07, 55) + (33) = (07, 33, 55)

(22) + (18) = (18, 22)

Новый набор чисел:

08, 13, 17, 24, 06, 11, 19, 20, 07, 33, 55, 18, 22, 02, 40

Этап 2. Выделяем в новом наборе серии и попарно сливаем их (число серий уменьшилось):

(08, 13, 17, 24), (06, 11, 19, 20), (07, 33, 55), (18, 22), (02, 40)

(08, 13, 17, 24) + (06, 11, 19, 20) = (06, 08, 11, 13, 17, 19, 20, 24)

(07, 33, 55) + (18, 22) = (07, 18, 22, 33, 55)

Новый набор:

06, 08, 11, 13, 17, 19, 20, 24, 07, 18, 22, 33, 55, 02, 40

Этап 3. Выделяем в новом наборе серии (всего три) и сливаем их:

(06, 08, 11, 13, 17, 19, 20, 24), (07, 18, 22, 33, 55), (02, 40)

(06, 08, 11, 13, 17, 19, 20, 24) + (07, 18, 22, 33, 55) = (06, 07, 08, 11, 13, 17, 18, 19, 20, 22, 24, 33, 55)

Новый набор и его две серии:

(06, 07, 08, 11, 13, 17, 18, 19, 20, 22, 24, 33, 55), (02, 40)

Этап 4. После слияния этих двух серий получим полностью упорядоченный набор:

02, 06, 07, 08, 11, 13, 17, 18, 19, 20, 22, 24, 33, 40, 55

Сбалансированное многолучевое слияние.

Массивы: 3, 5, 7, 44 5, 6, 30, 55 9, 23, 33, 45

Записываем меньшее: 3

3, 5, 7, 44 5, 6, 30, 55 9, 23, 33, 45

Записываем меньшее: 5

3, 5, 7, 44 5, 6, 30, 55 9, 23, 33, 45

Записываем меньшее: 5

3, 5, 7, 44 5, 6, 30, 55 9, 23, 33, 45

Записываем меньшее: 6

3, 5, 7, 44 5, 6, 30, 55 9, 23, 33, 45

Записываем меньшее: 7

3, 5, 7, 44 5, 6, 30, 55 9, 23, 33, 45

Записываем меньшее: 9

3, 5, 7, 44 5, 6, 30, 55 9, 23, 33, 45

Записываем меньшее: 23

3, 5, 7, 44 5, 6, 30, 55 9, 23, 33, 45

Записываем меньшее: 30

3, 5, 7, 44 5, 6, 30, 55 9, 23, 33, 45

Записываем меньшее: 33

3, 5, 7, 44 5, 6, 30, 55 9, 23, 33, 45

Записываем меньшее: 44

3, 5, 7, 44 5, 6, 30, 55 9, 23, 33, 45

Записываем меньшее: 45

3, 5, 7, 44 5, 6, 30, 55 9, 23, 33, 45

ПРИЛОЖЕНИЕ 1