Нисходящая сортировка слиянием

Эта сортировка является рекурсивной операцией, которая делит файл пополам и выполняет по рекурсии сортировку обеих половин. Дерево рекурсии выглядит следующим образом:

Рекурсия ограничена снизу размером разделяемого файла, равным 1. Каждый рекурсивный вызов делит файл пополам. В случае если размер файла кратен 2, получается полное, сбалансированное дерево рекурсии.

Если n не кратно 2, то дерево получается несбалансированным, но все равно его высота оценивается log2 n. Общий алгоритм нисходящей сортировки слиянием выглядит следующим образом:

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

Имея в своем распоряжении процедуру слияния, нетрудно положить ее в осно-

ву рекурсивной процедуры сортировки. Чтобы отсортировать заданный файл, нуж-

но разделить его на две части, рекурсивно отсортировать обе половины и затем слить

их. Реализация этого алгоритма представлена в программе 8.3; а пример показан на

рис. 8.2. Как было сказано в главе 5, этот алгоритм является одним из самых известных

примеров использования принципа “разделяй и властвуй” для разработки эффективных

алгоритмов.

Нисходящая сортировка слиянием аналогична принципу управления сверху вниз,

при котором руководитель разбивает большую задачу на подзадачи, которые должны

независимо решать его подчиненные. Если каждый руководитель будет просто разби-

вать свою задачу на две равные части, а потом объединять решения, полученные его

подчиненными, и передавать результат своему начальству, то получится процесс, ана-

логичный сортировке слиянием. Работа практически не продвигается, пока не получит

свою задачу кто-то, не имеющий подчиненных (в рассматриваемом случае это слияние

двух файлов размером 1); но потом руководство выполняет значительную работу, объе-

диняя результаты работы подчиненных.

Сортировка слиянием играет важную роль благодаря простоте и оптимальности

заложенного в нее метода (время ее выполнения пропорционально N log N), который допускает возможность устойчивой реализации. Эти утверждения сравнительно нетрудно доказать.

Эта базовая реализация сортировки слиянием является примером рекурсивной програм-

мы, основанной на принципе “разделяй и властвуй”. Для упорядочения массива a[1],

..., a[r] он разбивается на две части a[1],..., a[m] и a[m+1],..., a[r], которые сорти-

руются независимо друг от друга (через рекурсивные вызовы) и вновь сливаются для по-

лучения отсортированного исходного файла. Функции merge может потребоваться вспо-

могательный файл, достаточно большой для помещения копии входного файла, однако

эту абстрактную операцию удобно рассматривать как обменное слияние (см. текст).

template <class Item>

void mergesort(Item a[], int l, int r)

{ if (r <= l) return;

int m = (r+l)/2;

mergesort(a, l, m);

mergesort(a, m+1, r);

merge(a, l, m, r);

}

A S O R T I N G E X A M P L E

A S

O R

A O R S

I T

G N

G I N T

A G I N O R S T

E X

A M

A E M X

L P

E L P

A E E L M P X

A A E E G I L M N O P R S T X

Рис. 8.2. Пример нисходя-

Поиск по сайту: