SoloNasus - 1 year ago 111
C++ Question

# Merging two sorted arrays with for loop

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

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

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download