Void merge(int* a, int p, int q, int r)

{ int i, j, k, L= r – p + 1;

int* x = new int[L];

i = p; j = q + 1;

for (k = 0; k < L; k++) { if (j > r) { x[k] = A[i]; i++; continue; }

if (i > q) { x[k] = A[j]; j++; continue; }

if (A[i] <= A[j]) { x[k] = A[i]; i++; }

else { x[k] = A[j]; j++; }

}

for (k = 0; k < L; k++) A[p+k] = x[k];

delete[] x;

}

Главная процедура sort_merge выполняет сортировку произвольного отрезка массива A с числом элементов n и с границами [p,r].

Void sort_merge(int* a, int n, int p, int r)

{ int q;

if (p < r) { q = (p + r) / 2;

sort_merge(A, n, p, q); // рекурсивные вызовы

sort_merge(A, n, q+1, r); // функции merge_sort

merge(A, p, q, r);

}

}

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

sort_merge(a, n, 0, n-1);

Использование двух последних параметров в таком вызове связано с "рекурсивностью" функции sort_merge.

Основные элементы алгоритма:

- слияние двух упорядоченных массивов в один упорядоченный массив;

- рекурсия;

- операция упорядочения пары элементов.

Обозначим:

merge(A, p, q, r) - процедура слияния (предварительно упорядоченных) отрезков массива A[p .. q] и A[q+1 .. r] в отрезок A[p .. r] , q – номер среднего элемента отрезка [p .. r]. Если отрезок имеет четную длину, то q есть номер крайнего справа элемента левой половины отрезка. Будем для простоты считать, что n = 2 ^p .

sort_m(A, n, p, q) - процедура упорядочения методом слияния отрезка A[p .. q] массива A с размером n. Схема этой процедуры в общем выглядит так:

sort_m(A, n, p, r) // t = F(n)

{ if (n <= 2)

{ q = (p + r) / 2; // t = c₀

merge(A, p, q, r); // t = c₁n

}

if (n > 2)

{ q = (p + r) / 2; // t = c₀

sort_m(A, n, p, q); // t = F(n/2)

sort_m(A, n, q + 1, r); // t = F(n/2)

merge(A, p, q, r); // t = c₁n

}

}

Из текста следует:

Если n<=2, то F(2) = c₀ + 2c₁ ,

Если n > 2, то F(n) = с₀ + 2F(n/2) + c₁n .

Решение будем искать методом развертывания. Найдем F(n) для n = 8 :

F(8) = c₀ + 2F(4) + 8c₁ ,

F(4) = c₀ + 2F(2) + 4c₁ ,

F(2) = c₀ + 2c₁ .

Отсюда:

F(8) = c₀ + 8c₁ + 2(c₀ + 4c₁ + 2(c₀ + 2c₁)) = 7c₀ + 24c₁ = (8-1)c₀ + 8log₂(8)c₁

Обобщая на случай произвольного n, получаем:

F(n) = c₀ (n-1) + c₁ n log₂(n) . Отсюда, с учетом закона поглощения, имеем:

F(n) = (n log n) .

6. Метод вычерпывания

Пусть имеем числовой массив a[0] .. a[n-1] , все элементы которого имеют случайные значения, которые равномерно распределены на отрезке [a,b]. Разделим отрезок [a,b] на n интервалов и создадим n (вначале пустых) списков, по одному для каждого интервала. Алгоритм вычерпывания включает в себя два этапа:

1) распределим элементы исходного массива по соответствующим спискам;

2) упорядочим каждый из списков;

3) перепишем последовательно элементы каждого из списков в исходный массив a[0] .. a[n-1].

Доказано, что алгоритм вычерпывания имеет в среднем линейный порядок. Его функция сложности принадлежит асимптотическому классу (n).

Метод вычерпывания может быть применен и для упорядочивания не числовых массивов. Однако это возможно, если элементы исходного массива можно разделить на n групп, где n - размер исходного массива, таким образом, чтобы:

а) для любого i любой элемент группы с номером i+1 был больше любого элемента группы с номером i ;

б) среднее количество элементов исходного массива, принадлежащих группе с произвольным номером равно 1 или мало отличается от 1.

Подробнее о методе вычерпывания см. в [1-Кормен].