CLRS Merge Sort Help

[mpark4656]

I'm trying to implement the merge sort algorithm explained in Intro to Algorithm, but I am unable to produce the correct result. Can anyone look at the code and point out where the problem is? I must have done something wrong in the merge() function.

#include <iostream>

void merge( int arr[] , int low , int mid , int high )
{
    int n1 = mid - low + 1;
    int n2 = high - mid;

    int leftSubArray[n1 + 1];
    int rightSubArray[n2 + 1];

    for( int i = 0 ; i < n1 ; i++ ) {
        leftSubArray[i] = arr[low + i];
    }

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

    // Sentinel - Has to be larger than any element in the array
    leftSubArray[n1] = 1000000;
    rightSubArray[n2] = 1000000;

    int i = 0;
    int j = 0;

    for( int k = low ; k < high ; k++ ) {
        if( leftSubArray[i] <= rightSubArray[j] ) {
            arr[k] = leftSubArray[i];
            i++;
        }
        else {
            arr[k] = rightSubArray[j];
            j++;
        }
    }
}

void mergeSort( int arr[] , int low , int high )
{
    if( low < high ) {
        int mid = ( low + high ) / 2;

        mergeSort( arr , low , mid );
        mergeSort( arr , mid + 1 , high );
        merge( arr , low , mid , high );
    }
}

int main()
{
    int arr[7] = { 4 , 6 , 1 , 10 , 5 , 3 , 7 };
    mergeSort( arr , 0 , 6 );

    for( int i = 0 ; i < 7 ; i++ ) {
        std::cout << arr[i] << " ";
    }
}

[mpark4656]

Nevermind. I figured out my mistake

#include <iostream>

void merge( int arr[] , int low , int mid , int high )
{
    int n1 = mid - low + 1;
    int n2 = high - mid;

    int leftSubArray[n1 + 1];
    int rightSubArray[n2 + 1];

    for( int i = 0 ; i < n1 ; i++ ) {
        leftSubArray[i] = arr[low + i];
    }

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

    // Sentinel - Has to be larger than any element in the array
    leftSubArray[n1] = 1000000;
    rightSubArray[n2] = 1000000;

    int i = 0;
    int j = 0;

    for( int k = low ; k <= high ; k++ ) {
        if( leftSubArray[i] <= rightSubArray[j] ) {
            arr[k] = leftSubArray[i];
            i++;
        }
        else {
            arr[k] = rightSubArray[j];
            j++;
        }
    }
}

void mergeSort( int arr[] , int low , int high )
{
    if( low < high ) {
        int mid = ( low + high ) / 2;

        mergeSort( arr , low , mid );
        mergeSort( arr , mid + 1 , high );
        merge( arr , low , mid , high );
    }
}

int main()
{
    int arr[6] = { 4 , 6 , 1 , 5 , 3 , 7 };
    mergeSort( arr , 0 , 5 );

    for( int i = 0 ; i < 6 ; i++ ) {
        std::cout << arr[i] << " ";
    }
}