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

Нужно реализовать нисходящую сортировку слиянием методом абстрактного обменного слияния. Вот функция абстрактного обменного слияния:
template void merge(Item a[], int l, int m, int r) { int i, j; static Item aux[maxN]; for (i = m + 1; i > l; i--) aux[i - 1] = a[i - 1]; for (j = m; j < r; j++) aux[r + m - j] = a[j + 1]; for (int k = l; k <= r; k++) if (aux[j] < aux[i]) a[k] = aux[j--]; else a[k] = aux[i++]; }
Как сделать эту сортировку нисходящей, то есть рекурсивной?

Ответ

Я немного изменил вашу функцию. Среднее значение вычисляется внутри. Принцип работы алгоритма таков, что сначала исходный массив разбивается на два других. Каждый из них также разобьется ещё на два. Это будет продолжаться до тех пор, пока длина каждого подмассива будет равна 1.
template void merge(Item a[], int l, int r) {
if (abs(r - l) <= 1) return; //конец рекурсивных вызовов int i, j; int m = (l + r) / 2; merge(a, l, m); //вызов для левой части merge(a, m+1, r); //вызов для правой части static Item aux[1000]; for (i = m + 1; i > l; i--) aux[i - 1] = a[i - 1]; for (j = m; j < r; j++) aux[r + m - j] = a[j + 1]; for (int k = l; k <= r; k++) { if (aux[j] < aux[i]) a[k] = aux[j--]; else a[k] = aux[i++]; } }
Замечание: при вызове функции необходимо указывать длину массива - 1. То есть:
int main() { int a[N]; merge(a, 0, N-1); }