Странное поведение алгоритма сортировки слиянием в C ++

Question

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

КОД: -

#include <bits/stdc++.h>

using namespace std;

int merge(int *ar, int l, int r) {
    int aux[r - l + 1], s1 = 0, s2 = (r - l) / 2 + 1;

    for (int i = 0; i < r - l + 1; i++)
        aux[i] = ar[l + i];
    for (int k = 0; k < r - l + 1; k++) {
        if (s1 > ((r - l) / 2))
            ar[l + k] = aux[s2++];
        else
        if (s2 > r)
            ar[l + k] = aux[s1++];
        else
        if (aux[s1] <= aux[s2])
            ar[l + k] = aux[s1++];
        else
            ar[l + k] = aux[s2++];
    }
    //for (int i = 0; i < 17; i++) cout << ar[i] << " ";
    //cout << endl;
    return 0;
}

void  mergesort(int *ar, int l, int r) {
    if (l >= r)
        return;
    int mid = (l + r) / 2;
    mergesort(ar, l, mid);
    mergesort(ar, mid + 1, r);
    merge(ar, l, r);
}

int main() {
    int ar[] ={ 34, 54, 56, 42, 32, 46, 99, 85, 5, 45, 34, 54, 6, 56, 54, 64, 5 },
        l = 0, r = sizeof(ar) / sizeof(int) - 1;
    mergesort(ar, l, r);
    for (int i = 0; i < r + 1; i++)
        cout << ar[i] << " ";
    return 0;
}

ВЫХОД: -

5 5 6 16 16 16 32 16 34 34 16 46 54 54 16 56 99

Я не знаю, откуда берутся эти 16, этого не происходит для массива одиночных чисел di git любой длины и небольших массивов из 2 di git числа. Кроме того, если я cout что-нибудь в функции merge (например, пробелы, табуляции, новые строки или любое число), я получаю правильный результат, т.е.

        5 5 6 32 34 34 42 45 46 54 54 54 56 56 56 64 99

[Я напечатал здесь пробелы.]

Пытался изменить параметры функции, но это не помогает. Пожалуйста, помогите, я не могу разобраться в этом самостоятельно.

Answer 1

В функции merge тест if (s2 > r) неверен. Это должно быть if (s2 > r - l).

Очень сложно передавать r в качестве индекса последнего элемента. В C и C ++ более идиоматично c передавать индекс элемента после последнего, поэтому r - l будет длиной массива. При таком подходе отсутствуют настройки, подверженные ошибкам +1 / -1.

Вот модифицированная версия:

#include <iostream>

using namespace std;

void merge(int *ar, int l, int r) {
    int len = r - l;
    int mid = len / 2;
    int s1 = 0, s2 = mid;
    int aux[len];

    for (int i = 0; i < len; i++)
        aux[i] = ar[l + i];
    for (int k = l; k < r; k++) {
        if (s1 >= mid)
            ar[k] = aux[s2++];
        else
        if (s2 >= len)
            ar[k] = aux[s1++];
        else
        if (aux[s1] <= aux[s2])
            ar[k] = aux[s1++];
        else
            ar[k] = aux[s2++];
    }
}

void mergesort(int *ar, int l, int r) {
    if (r - l >= 2)
        return;
    int mid = l + (r - l) / 2;
    mergesort(ar, l, mid);
    mergesort(ar, mid, r);
    merge(ar, l, r);
}

int main() {
    int ar[] = { 34, 54, 56, 42, 32, 46, 99, 85, 5, 45, 34, 54, 6, 56, 54, 64, 5 };
    int len = sizeof(ar) / sizeof(ar[0]);
    mergesort(ar, 0, len);
    for (int i = 0; i < len; i++)
        cout << ar[i] << " ";
    cout << endl;
    return 0;
}