Неупорядоченная цепочка элементов

Случаем, когда не делится без остатка на 2 можно пренебречь, приняв остаток за независимую (отдельную) цепочку, которая может быть объединена или нет на каждом из этапов процесса объединения. Пример процесса сортировки методом объединения для последовательности, состоящей из 35 элементов (здесь просто ключей), приведен ниже.
Неупорядоченная цепочка элементов, каждый из которых имеет порядок, может быть обработана в соответствии с блок-схемой. Здесь за основу взята блок-схема с параметрами. Введем два индекса: число полных объединений, которые были выполнены, и число объединений цепочек, состоящих из элементов, которое было выполнено для данного значения. Для выполнения описываемого приема, когда он представлен подпрограммой, основная программа вырабатывает значения, которые служат в качестве описанного метода объединения, и адреса.

(Выполнение операций вычисления адресов не включено в блок-схему, чтобы не усложнять ее, но совершенно ясно, как это сделать.) В самом неблагоприятном случае, когда элементы информации упорядочены в противоположном направлении, число сравнений, необходимых для упорядочения элементов, которое можно считать мерой эффективности описываемого метода, может быть выведено из предыдущих рассуждений.
Легко показать, что целое число, а общую оценку можно получить несколько более сложными рассуждениями. Для наиболее благоприятного случая, когда элементы информации двух цепочек уже упорядочены, число сравнений может быть минимальным. При этом потребуется усложнить блок-схему, а следовательно, и переделать программу для того, чтобы воспользоваться возможной почти полной упорядоченностью исходных цепочек. Детализация метода в этом случае зависит от того, сколько элементов информации может одновременно находиться в оперативной памяти.

Источник: delete-it