8.29. Предположим, что размер файла является степенью 2. Удалите рекурсию из нисходящей сортировки слиянием, чтобы получить нерекурсивную сортировку слиянием, которая выполняет ту же последовательность слияний.

8.30. Доказать, что количество проходов, выполняемых нисходящей сортировкой слиянием, также представляется числом бит в двоичном представлении (см. лемму 8.6).

8.6. Производительность сортировки слиянием

Таблица 8,1 характеризует относительную эффективность различных усовершенствований из числа рассмотренных выше. Как это часто бывает, такие исследования показывают, что время выполнения сортировки можно сократить наполовину и даже больше, если направить усилия на улучшения внутреннего цикла алгоритма сортировки.

Помимо погони за усовершенствованиями, рассмотренными в разделе 8.2, можно добиться дальнейших улучшений производительности за счет того, что наименьшие элементы в обоих массивах будут содержатся в простых переменных или в регистрах процессора во избежание ненужных доступов к массивам. Таким образом, внутренний цикл сортировки слиянием может быть, в основном, сведен к операциям сравнения (с условным переходом), к увеличению на единицу значений двух счетчиков (к и одного из i или j) и проверке условия завершения цикла с условным переходом. Общее количество команд во внутреннем цикле несколько превышает этот показатель для быстрой сортировки, однако такие команды выполняются всего лишь N IgN раз, в то время как команды внутреннего цикла выполняются в рамках быстрой сортировки на 39 процентов чаще (или на 29 процентов в случае ее варианта с вычислением медианы из трех элементов). Чтобы выполнить точное сравнение этих двух алгоритмов в конкретной среде, следует воспользоваться более совершенной реализацией и провести более подробный анализ. Тем не менее, точно известно, что внутренний цикл сортировки слиянием несколько длиннее внутреннего цикла быстрой сортировки.

РИСУНОК 8.7. СРАВНЕНИЕ ВОСХОДЯЩЕЙ СОРТИРОВКИ СЛИЯНИЕМ С НИСХОДЯЩЕЙ СОРТИРОВКОЙ СЛИЯНИЕМ

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

Таблица 8.1. Эмпирические исследования алгоритмов сортировки шиянием

Представленные здесь относительные временные показатели различных видов сортировки на файлах чисел с плавающей точкой с произвольной организацией для различного числа N отражают следующие факты: стандартная быстрая сортировка выполняется в два раза быстрее стандартной сортировки слиянием; добавление отсечения файлов небольших размеров снижает время выполнения нисходящей и восходящей сортировок слиянием примерно на 15 процентов; для заданных в таблице размеров файлов быстродействие нисходящей сортировки слиянием примерно на 10 процентов выше, чем восходящей; даже если устранить затраты на копирование файла, то и в этом случае сортировка слиянием файлов с произвольной организацией на 50-60 процентов медленнее простой быстрой сортировки (см. табл. 7.1).

Ключи:

Q Стандартная быстрая сортировка (программа 7.1)

Т Сортировка нисходящая слиянием, стандартная (программа 8.1)

Т* Сортировка нисходящая слиянием с отсечением файлов небольших размеров

О Сортировка нисходящая слиянием с отсечением и без копирования массива

В Стандартная сортировка восходящая слиянием (программа 8.5)

В* Сортировка восходящая слиянием с отсечением файлов небольших размеров

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

РИСУНОК 8.8. ВОСХОДЯЩАЯ СОРТИРОВКА СЛИЯНИЕМ РАЗЛИЧНЫХ ВИДОВ ФАЙЛОВ

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