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);
    }

}

Please post a `main` function with the test data that you are calling these functions with. — PaulMcKenzie, Aug 20 '21 at 03:40
In other words, please provide a [mre]. If possible, please hard-code your input into the function `main`, but verify that this input is actually triggering the problem before posting it. — Andreas Wenzel, Aug 20 '21 at 03:45
Also, you don't need to do these "tricks" using infinity to write a generic merge sort. Note that this is not needed [here](https://stackoverflow.com/questions/24650626/how-to-implement-classic-sorting-algorithms-in-modern-c) (scroll down to the **Merge Sort** implementation). — PaulMcKenzie, Aug 20 '21 at 03:47
You're making that merge *way* more complicated than it needs to be. — WhozCraig, Aug 20 '21 at 03:50

score 1 · Answer 1 · answered Aug 21 '21 at 12:16

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);
    }

}

score 0 · Answer 2 · answered Aug 20 '21 at 04:03

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;
}

You didn't answer the OP's question -- what was wrong with his version of MergeSort? Also, this: `double temp[end + 1 - start];` is not valid C++. — PaulMcKenzie, Aug 20 '21 at 04:17
Just for clarification of the previous comment: ISO C++ does not support [variable-length arrays](https://en.wikipedia.org/wiki/Variable-length_array), although some compilers do support it as an extension. — Andreas Wenzel, Aug 20 '21 at 05:31

What is wrong with my Implementation of MergeSort

2 Answers2