SoloNasus - 10 days ago 5x

C++ 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

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

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

Source (Stackoverflow)

Comments