Характеристики метода. Имея М частей размера Z и начав со слияния двух из них, будем сливать все следующие с

Имея М частей размера Z и начав со слияния двух из них, будем сливать все следующие с большей (растущей) упорядоченной частью. Она как бы поглощает часть за частью. Упорядочивание каждой исходной части производят непосредственно перед ее поглощением.

В начале сортировки считывается окончание файла, упорядочивается в памяти и возвращается на место.

Перед поглощением очередная часть файла считывается в зону “А” памяти, там упорядочивается и остается. Начало ранее упорядоченной части считывается в зону “В”, после чего начинается слияние, прерываемое считыванием в зону “В”, когда она опустошается.

По мере заполнения зоны “С” записями результата слияния, содержимое ее переписывается в файл (на место поглощаемой части и далее в сторону конца файла).

Если при слиянии взяты все записи поглощаемой части, поглощение завершается передачей из зоны “С” в файл остатка результата. Слияние также завершается, если исчерпана ранее упорядоченная часть. Поглощение ею очередной части произошло.

Затем выполняется ход от конца файла до начала ближайшей неупорядоченной части. К концу процесса количество ходов достигнет, таким образом, значения М-1, причем с каждым разом ход будет все длиннее - начиная от сегмента размером 2Z и кончая сегментом размером МZ. Таким образом, в среднем размер прогона составит 0.5МZ. Этот размер и опредеяет среднюю сложность этапа. Для всех этапов получаем оценку 0.5МZ (М-1), откуда сложность метода поглощения составит T(М)=O(ZM^²).

Дата добавления: 2015-08-17