c++ - Sort array using merge sort

Question

I am using merge sort for descending my array. What is the reason that my first element changed his value? My half code works. But with my first and last elements something went wrong.

#include <iostream>

void Merge(int a[], int low, int high, int mid)
{
    int i = low, j = mid + 1, k = 0;
    int temp[high - low + 1];

    while (i <= mid && j <= high) {
        if (a[i] > a[j])
            temp[k++] = a[i++];

        else
            temp[k++] = a[j++];
    }

    while (i <= mid) {
        temp[k++] = a[i++];
    }

    while (j <= high) {
        temp[k++] = a[j++];
    }
    for (i = low; i <= high; i++) {
        a[i] = temp[i - low];
    }
    return;
}

void MergeSort(int a[], int low, int high)
{
    int mid;
    if (low < high) {
        mid = (low + high) / 2;
        MergeSort(a, low, mid);
        MergeSort(a, mid + 1, high);

        Merge(a, low, high, mid);
    }

    return;
}

void output(int* a, int n)
{
    for (int i = 0; i < n; i++) {
        std::cout << a[i] << "";
    }
}

int main()
{
    int n;
    std::cin >> n;
    int a[n];
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
    }
    MergeSort(a, 0, n);
    output(a, n);
}

The output must be this.

input 10

1 2 3 4 5 6 7 8 9 10

output

10 9 8 7 6 5 4 3 2 1

But I'm getting this output

4197055 10  9   8   7   6   5   4   3   2 

I'm a beginner in a c++. So I will be happy if you can help me to do my first steps here.

question from:https://stackoverflow.com/questions/65942286/sort-array-using-merge-sort

Answer 1

You have mixed up how ranges of indexes are described. In same cases you have made those ranges closed at the end and in other opened at the end. Result is undefined behavior buffer overrun.

Here is fixed version where low points to first element and high point one step beyond last element.

Remember that in C++ indexes of array arr[n] should be from 0 to n - 1 inclusive.

void Merge(int a[], int low, int high, int mid)
{
    int i = low, j = mid, k = 0;
    int temp[high - low];

    while (i < mid && j < high) {
        temp[k++] = a[i] < a[j] ? a[i++] : a[j++];
    }

    while (i < mid) {
        temp[k++] = a[i++];
    }

    while (j < high) {
        temp[k++] = a[j++];
    }

    for (i = low; i < high; i++) {
        a[i] = temp[i - low];
    }
    return;
}

void MergeSort(int a[], int low, int high)
{
    int mid;
    if (low + 1 < high) {
        mid = (low + high) / 2;
        MergeSort(a, low, mid);
        MergeSort(a, mid, high);

        Merge(a, low, high, mid);
    }

    return;
}

https://godbolt.org/z/nET5YT