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

#cpp #алгоритм #сортировка

Нужно реализовать нисходящую сортировку слиянием методом абстрактного обменного слияния.
Вот функция абстрактного обменного слияния:

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

Я немного изменил вашу функцию. Среднее значение вычисляется внутри. Принцип работы
алгоритма таков, что сначала исходный массив разбивается на два других. Каждый из них
также разобьется ещё на два. Это будет продолжаться до тех пор, пока длина каждого
подмассива будет равна 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);
}