Merge two sorted arrays

Question

This is my code for merging 2 sorted arrays:

#include<iostream>

using namespace std;

void merge(int arr1[], int n, int arr2[], int m, int arr3[]) {

    int i = 0, j = 0;
    int k = 0;
    while( i<n && j<m) {
        if(arr1[i] < arr2[j]){
            arr3[k++] = arr1[i++];
        }
        else{
            arr3[k++] = arr2[j++];
        }
    }
    
}

void print(int ans[], int n) {
    for(int i=0; i<n; i++) {
        cout<< ans[i] <<" ";
    }
    cout << endl;
}

int main() {

    int arr1[5] = {1,3,5,7,9};
    int arr2[3] = {2,4,6};

    int arr3[8] = {0};

    merge(arr1, 5, arr2, 3, arr3);

    print(arr3, 8);


    return 0;
}

I expect to get the output:

1 2 3 4 5 6 7 9

But instead the output I get is:

1 2 3 4 5 6 0 0

What is the cause of that ?

Answer 1

You forgot one thing!

If arr1 is 1,2,3 and arr2 is 4,5,6. Then you will only copy arr1 into arr3. You need to do the loop you have written; BUT then when you exit the loop one of the arrays will have items still left to copy and you simply need to copy the remaining elements.

void merge(int arr1[], int n, int arr2[], int m, int arr3[])
{
    int i = 0, j = 0;
    int k = 0;
    while (i < n && j < m)
    {
        if(arr1[i] < arr2[j]){
            arr3[k++] = arr1[i++];
        }
        else{
            arr3[k++] = arr2[j++];
        }
    }

    // Copy any remaining elements.
    // Note: Only one of these loops will do any work
    //       The other loop is a noop.
    while (i < n) {
        arr3[k++] = arr1[i++];
    }
    while (j < m) {
        arr3[k++] = arr2[j++];
    }    
}

We can simplify a couple of things:

        if(arr1[i] < arr2[j]){
            arr3[k++] = arr1[i++];
        }
        else{
            arr3[k++] = arr2[j++];
        }


        // Could be written as:

        arr3[k++] = (arr1[i] < arr2[j]) ? arr1[i++] : arr2[j++];

The tertiary operator is a shortcut operator and only one side is evaluated.

---

Other things to note about C++

merge(arr1, 5, arr2, 3, arr3);

This would be better written as:

// Do not hard code the length of the array.
// Somebody in the future will come along and change the
// array and not look to where it is used and thus cause
// an error. Use `std::size()` to get the length of the array.
merge(arr1, std::size(arr1), arr2, std::size(arr2), arr3);

I would also change the operation to use iterators. This makes it easier to use some of the standard functions.

template<typename I1, typename I2, typename I3>
void merge(I1 b1, I1 e1, I2 b2, I2, e2, I3 dst)
{
    while (b1 < e1 && b2 < e2)
    {
        *dst++ = (*b1 <= *b2) ? *b1++ : *b2++;
    }
    dst = std::copy(b1, e1, dst);
    dst = std::copy(b2, e2, dst);
}

Then you can use it like:

merge(std::begin(arr1), std::end(arr1),
      std::begin(arr2), std::end(arr2),
      std::begin(arr3));

Answer 2

You have to consider the edge case:- when one of the linked lists ends. Then you have to loop through the other list and add the remaining elements.

So in your case, arr2 has 3 values and arr1 has 5 values. So your while loop ends when one of the list elements ends. So in the above case, arr2 will end so you have to add arr1 elements in arr3

After a while loop, you have to add this code

    while (i < arr1.size()) arr3[k++] = arr1[i++];

    while (j < arr2.size()) arr3[k++] = arr2[j++];
   

Answer 3

You need to handle the case where you reached the end of the shorter list, and need to copy the rest of the longer one.
This is handled in the code below by the 2 additional while loops.

Also it's advisable to use std::vectors instead of old c style arrays. It will save you the need to manually track the array sizes.

#include <iostream>
#include <vector>

void merge(std::vector<int> const & arr1, std::vector<int> const & arr2, std::vector<int> & arr3) {
    int i = 0, j = 0;
    int k = 0;
    arr3.resize(arr1.size() + arr2.size());
    while (i < arr1.size() && j < arr2.size()) {
        if (arr1[i] < arr2[j]) {
            arr3[k++] = arr1[i++];
        }
        else {
            arr3[k++] = arr2[j++];
        }
    }
    // Copy the rest of arr1 (if needed):
    while (i < arr1.size()) {
        arr3[k++] = arr1[i++];
    }
    // Copy the rest of arr2 (if needed):
    while (j < arr2.size()) {
        arr3[k++] = arr2[j++];
    }
}

void print(std::vector<int> const & ans) {
    for (size_t i = 0; i < ans.size(); i++) {
        std::cout << ans[i] << " ";
    }
    std::cout << std::endl;
}

int main() {
    std::vector<int> arr1 = { 1,3,5,7,9 };
    std::vector<int> arr2 = { 2,4,6 };
    std::vector<int> arr3;
    merge(arr1, arr2, arr3);
    print(arr3);
    return 0;
}

Output:

1 2 3 4 5 6 7 9

A side note: better to avoid using namespace std - see here Why is "using namespace std;" considered bad practice?.

Answer 4

Assume for a second that there are "sentinel" values arr1[n] == arr2[m] == ∞. Then the code below would work, as it will fully traverse both arrays, without going past (mind the ||).

int i = 0, j = 0 k = 0;
while (i < n || j < m) {
    if (arr1[i] < arr2[j]) {
        arr3[k++]= arr1[i++];
    }
    else {
        arr3[k++]= arr2[j++];
    }
}

Now you can emulate the presence of the sentinels by refining the comparison condition:

arr1[i] < arr2[j]

becomes

(i < n && j < m && arr1[i] < arr2[j]) || (i < n && j >= m)

which can be written

i < n && (j >= m || arr1[i] < arr2[j])

(check the cases n == i and m == j).

Notice that it is more efficient to split the code in three successive loops, processing separately the situations where one of the arrays has been fully seen.

Answer 5

this loop

while( i<n && j<m) {

stops when you reach the end of the shortest array. In this case, when m=3. You need to continue to copy the remaining elements from the larger array