Merging two sorted arrays with for loop

Question

I have a function that merges two sorted arrays into one and returns a pointer to it. I want to use a for loop rather than a while. However in some test cases the last 1 or 2 elements of the merge array are not in their place. I would appreciate if someone can help solve this problem keeping the for loop.

int * mergeSort(int arr1[], int arr2[],int len)
{

  /* len is the combined length of the two arrays */

    static int sorted[100];

    int pos1=0, pos2=0;

    for (int i=0; i<len; i++)
    {
        if (arr1[pos1]<=arr2[pos2])
        {
            sorted[i]=arr1[pos1];
            pos1++;
        }
        else
        {
            sorted[i]=arr2[pos2];
            pos2++;
        }
    }

    return sorted;
}

Answer 1

Your problem is that you don't seem to handle going past the end of the input arrays. If there is uninitialized memory - you get undefined behaviour.

You can avoid this by terminating your arrays with a sentinel value, for example INT_MAX, which should always be bigger than all possible values in the arrays:

int a[] = { 1, 2, 104, INT_MAX};
int b[] = { 101, 102, 105, INT_MAX};

int* ptr = mergeSort(a,b,6);

for(int i = 0; i < 6; i++){
    cout << i << " " << ptr[i] << endl;
}

live demo

Or you can pass the actual lengths of both arrays and handle them correctly:

int * mergeSort(int arr1[], int len1, int arr2[],int len2)
{

  /* len is the combined length of the two arrays */

    static int sorted[100];

    int pos1=0, pos2=0;

    for (int i=0; i< len1 + len2; i++)
    {
        if ((pos2 == len2) || (arr1[pos1] <= arr2[pos2] && (pos1 < len1)))
        {
            sorted[i]=arr1[pos1];
            pos1++;
        }
        else
        {
            sorted[i]=arr2[pos2];
            pos2++;
        }
    }

    return sorted;
}

live demo