31. Алгоритм прямого слияния.

На первом шаге упорядоченные отрезки имеют длину, равную единице, т.е. состоят из одного элемента.

Затем они объединяются и в случае двухпутевого слияния вновь сформированные отрезки будут состоять из двух элементов, а в случае многопутевого – из N элементов.

• Предположим, что имеется последовательный файл F0, состоящий из записей a₁, a₂, ..., a_n.

• Будем считать, что каждая запись состоит ровно из одного элемента, представляющего собой ключ сортировки.

• Для сортировки используются два вспомогательных файла F1 и F2 (размер каждого из них будет n/2).

• Сортировка состоит из последовательности шагов, в каждом из которых выполняется распределение состояния файла F0 в файлы F1 и F2, а затем слияние файлов F1 и F2 в файл F0.

• На первом шаге для распределения последовательно читается файл F0, и

• записи a₁, a₃, ..., a_n-1 пишутся в файл F1,

• а записи a₂, a₄, ..., a_n - в файл F2 (начальное распределение).

• Начальное слияние производится над парами (a₁, a₂), (a₃, a₄), ..., (a_n-1, a_n), и результат записывается в файл F0.

• На втором шаге снова последовательно читается файл F0,

  • и в файл F1 записываются последовательные пары с нечетными номерами,

  • а в файл F2 - с четными.

• При слиянии образуются и пишутся в файл F0 упорядоченные четверки записей.

• И так далее.

• Перед выполнением последнего шага файл F0 будет содержать две упорядоченные подпоследовательности размером n/2 каждая. При распределении

  • первая из них попадет в файл F1,

  • а вторая - в файл F2.

• После слияния файл F0 будет содержать полностью упорядоченную последовательность записей.

• Сортировка прямым слиянием заканчивается, если:

  • после фазы слияния длина серии не меньше количества элементов в файле;

  • на фазе слияния осталась ровно одна серия;

  • второй по счету вспомогательный файл для однофазной сортировки после распределения серий остался пустым.

31. Алгоритм естественного слияния.

Всегда сливаются две самые длинные из возможных серий, т.е. объединяются серии максимальной, а не заранее фиксированной длины.

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

В каждом проходе число серий уменьшается в N раз (если количество серий во вспомогательных файлах одинаково), а общее число пересылок не более, чем n ∗ [log n].

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

Так же как и прямое слияние, сортировка естественным слиянием может быть

1. двухпутевой или многопутевой,

2. двухфазной или однофазной.

При распределении распознается

3. первая серия записей и переписывается в файл F1,

4. вторая - в файл F2 и т.д.

При слиянии

5. первая серия записей файла F1 сливается с первой серией файла F2,

6. вторая серия F1 со второй серией F2 и т.д.

Если просмотр одного файла заканчивается раньше, чем просмотр другого (по причине разного числа серий), то остаток недопросмотренного файла целиком копируется в конец файла F0.

Процесс завершается, когда в файле F0 остается только одна серия.

• Пусть исходный файл состоит из элементов:

F0: 1 3 14 6 8 9 2 4 5 8 2 3 1 16

• Тогда двухпутевое двухфазное естественное слияние будет проходить следующим образом:

Проход	Распределение	Слияние
1	F1: 1 3 14 ‘ 2 4 5 8 ‘ 1 16 F2: 6 8 9 ‘ 2 3	F0: 1 3 6 8 9 14 2 2 3 4 5 8 1 16
2	F1: 1 3 6 8 9 14 ‘ 1 16 F2: 2 2 3 4 5 8 ‘	F0: 1 2 2 3 3 4 5 6 8 8 9 14 1 16
3	F1: 1 2 2 3 3 4 5 6 8 8 9 14 F2: 1 16	F0: 1 1 2 2 3 3 4 5 6 8 8 9 14 16

• Для упорядочивания данных в сортировке прямым слиянием при тех же самых условиях потребовалось бы 4 прохода, поскольку длина серии на 4-ом проходе составляла бы 16 элементов, а в исходном файле содержится 14 элементов.