Infinite loop problem with the merge sort during the portion recursively calls mergeSort

Question

Im working on a homework assignment comparing both execution time and theoretical O-notation of 10 separate sorts. However, as the question says I keep having an infinite loop when I get to the point that the code recursively calls merge sort. I know that it is when the left is at 2 and the right is at 3 so middle continuously returns as 3. is merge supposed to be outside of the if statement? I don't think that would be right either though when I look at it.

void merge(int arr[], int left, int middle, int right)
{
    // get the temporary array lengths
    int first = middle - left + 1;
    int second = right - middle;

    // make the temp dynamic arrays
    int *Left = new int(first);
    int *Right = new int(second);
    for (int i = 0; i < first; i++)
    {
       Left[i] = arr[left + i];
    }
    for (int i = 0; i < second; i++)
    {
        Right[i] = arr[middle + 1 + i];
    }

    // merge the arrays back into arr
    int i = 0;
    int j = 0;
    int k = left;

    while (i < first && j < second)
    {
        // check which one is bigger
        if (Left[i] <= Right[j])
        {
            arr[k] = Left[i];
            i++;
        }
        else
        {
            arr[k] = Right[j];
            j++;
        }
        k++;
    }
    // copy Left remainder
    while (i < first)
    {
        arr[k] = Left[i];
        i++;
        k++;
    }
    // copy right remainder
    while (j < second)
    {
        arr[k] = Right[j];
        j++;
        k++;
    }
}

void mergeSort(int arr[], int left, int right)
{
    if (left < right)
    {
        int middle = left + (right - 1) / 2;
        mergeSort(arr, left, middle);
        mergeSort(arr, middle + 1, right);
        merge(arr, left, middle, right);
    }
}

Answer 1

In mergeSort function, you forgot parenthesis when calculating middle. It should be:

int middle = (left + (right - 1)) / 2;

Also, in merge function, Left and Right should have type int[]. Instead of new int(SIZE), you should use new int[SIZE]. Moreover, you should use delete[] to delete them before leaving the function to prevent memory leak.

// make the temp dynamic arrays
int* Left = new int[first];
int* Right = new int[second];

// ...

// at the end of the `merge` function
delete[] Left;
delete[] Right;