What is wrong with my Implementation of MergeSort

  array-algorithms, c++, mergesort

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

}

Source: Windows Questions C++

LEAVE A COMMENT