What is wrong with my Implementation of MergeSort

Question

I have tried logging from inside the "MergeSort" to see what is wrong and outputting the array A after it has been modified and I am seeing bizarre values like 980498560986, they as though they mite be unallocated memory or memory addresses.

Any help is greatly appreciated.

infinity is used for the edge case of one sub array being solved before the other and the code used for it only works on doubles and floats or else I would have used integers.

void Merge(double A[], size_t start, size_t mid, size_t end)
{
    size_t n1 = mid - start;
    size_t n2 = end - mid;
    size_t i = 0;
    size_t j = 0;

    double* left = new double[n1 + 1];
    double* right = new double[n2 + 1];
    for (; i < n1; i++)
    {
        if (start == 0)
        {
            std::cout << A[start + i] << " ";
        }
        else
        {
            std::cout << A[start + i - 1] << " ";
        }
    }

    for (; i < n1; i++)
    {
        if (start == 0)
        {
            left[i] = A[start + i];
        }
        else
        {
            left[i] = A[start + i - 1];
        }
    }
    for (; j < n2; j++)
    {
        right[j] = A[mid + j];
    }

    left[n1] = std::numeric_limits<double>::infinity();
    right[n2] = std::numeric_limits<double>::infinity();

    i = 0;
    j = 0;
    for (size_t k = start; k < end; k++)
    {
        if (left[i] <= right[j])
        {
            A[k] = left[i];
            i++;
        }
        else
        {
            A[k] = right[j];
            j++;
        }
    }

    delete[] left;
    delete[] right;

}

void MergeSort(double A[], size_t start, size_t end)
{
    if (start < end)
    {
        size_t mid = (start + end) / 2; // int type floors naturally.
        MergeSort(A, start, mid);
        MergeSort(A, mid + 1, end);
        Merge(A, start, mid, end);
    }

}

Answer 1

I was indexing the arrays wrong, this is the corrected version.

void Merge(double A[], size_t start, size_t mid, size_t end)
{
    size_t n1 = mid - start;
    size_t n2 = end - mid;
    size_t i = 0;
    size_t j = 0;

   double* left = new double[n1 + 1];
   double* right = new double[n2 + 1];

   for (; i < n1; i++)
   {
       left[i] = A[start + i];
    }
    for (; j < n2; j++)
    {

        right[j] = A[mid + j];

    }

    left[n1] = std::numeric_limits<double>::infinity();
    right[n2] = std::numeric_limits<double>::infinity();

    i = 0;
    j = 0;
    for (size_t k = start; k < end; k++)
    {
       if (left[i] <= right[j])
       {
           A[k] = left[i];
           i++;
       }
       else
       {
           A[k] = right[j];
           j++;
       }
    }

    delete[] left;
    delete[] right;

}

void MergeSort(double A[], size_t start, size_t end)
{
    if (start < end)
    {
        size_t mid = (start + end) / 2; // int type floors naturally.
        MergeSort(A, start, mid);
        MergeSort(A, mid + 1, end);
        Merge(A, start, mid, end);
    }

}

Answer 2

Your code, rectified:

#include <bits/stdc++.h>
using namespace std;

void Merge(double A[], int start, int end)
{
    double temp[end + 1 - start];
    // Temporary array
    
    // Can calculate mid in this function
    int mid = start + (end - start) / 2;
    
    // i points to the start of left half
    // j points to the start of right half
    int i = start, j = mid + 1;
    
    // k points to the start of Temporary array
    int k = 0;
    
    // Pick smaller values from both the halves
    // And increment the pointers accordingly
    while(i <= mid && j <= end) {
        if(A[i] <= A[j]) {
            temp[k++] = A[i++];
        }
        else {
            temp[k++] = A[j++];
        }
    }
    
    // When there are elements still left in the first half
    while(i <= mid) {
        temp[k++] = A[i++];
    }
    
    // When there are elements still left in the second half
    while(j <= end) {
        temp[k++] = A[j++];
    }
    
    // Copy the contents of Temporary array into main array
    for(i = start, k = 0; i <= end; i++, k++) {
        A[i] = temp[k];
    }
}

void MergeSort(double A[], int start, int end)
{
    if (start < end)
    {
        size_t mid = start + (end - start) / 2;
        MergeSort(A, start, mid);
        MergeSort(A, mid + 1, end);
        Merge(A, start, end);
    }

}


int main() {
    
    double arr[] = {3.0, 1.0, 4.0, 2.1, 6.4, 3.1, 8.93};
    MergeSort(arr, 0, 6);
    for(int i = 0; i < 7; i++) {
        cout << arr[i] << " ";
    }
    
    return 0;
}