C++ Crashing in mergesort Function

Question

For some reason, my program keeps crashing while it's in this mergeSort function which has a purpose just to merge sort an array of data. In this case, I'm using an array of strings.

Here is the merge sort function code:

template <class T>
void Metrics<T>::mergeSort(T *arr, int n)
{

if ( n < 10 ) 
{
    insertionSort(arr,n);
    return;
}

int mid = n / 2;
int mid2 = n - mid;

T *Left = new T[mid];
T *Right = new T[mid2];

for ( int i = 0; i < mid; i++ )
{
    Left[i] = arr[i];
}

for ( int i = 0; i < mid2; i++ )
{
    Right[i] = arr[mid+i];
}

mergeSort(Left, mid);
mergeSort(Right,mid);

merge(Left,mid,Right,mid2,arr);

delete Left;
delete Right;
}

and Here is the merge function used in the mergeSort function:

template <class T>
void Metrics<T>::merge(T *a, int numA, T *b, int numB, T *c)
{
int i, j, k;
i = j = k = 0;

while ( i < numA && j < numB )
{
    if (a[i] <= b[j])
    {
        c[k] = a[i];
        i++;
        k++;
    }
    else
    {
        c[k] = b[j];
        j++;
        k++;
    }
}

while ( i < numA )
{
    c[k] = a[i];
    i++;
    k++;
}

while ( j < numB )
{
    c[k] = b[j];
    j++;
    k++;
}
}

The initial parameters I'm sending into the mergeSort function is just an array of strings, and the int n is 36. Oh and by the way, the insertion sort code is this:

template <class T>
void Metrics<T>::insertionSort(T *arr, int n)
{
for ( int i = 1; i < n; i++ )
{
    int j = i;

    while ( j > 0 && arr[j] < arr[j-1] )
    {
        T temp = arr[j];
        arr[j] = arr[j-1];
        arr[j-1] = temp;
        j--;
    }
}
}

I'm pretty sure it has to do with the fact that I'm sending in an array of strings into the function. It works when it's just with integers and characters though. Thanks!

EDIT:: After looking into it a little bit, I think it crashes on the "Delete Left" and "Delete Right" code on the bottom of mergeSort. Is there a reason for that? How can I fix it? Is that why it's crashing?

Answer 1

You should be using delete [] Left and delete [] Right to match the new [] calls.

Also you call to mergeSort(Right,mid); should be mergeSort(Right,mid2); but I don't think that would cause a crash, just a non-sorted item when n was odd.