C++ program to merge two unsorted arrays

In this article, we will write a program to merge two unsorted arrays. The output is the sorted array in ascending order.

Input : a[] = {10, 5, 15}

b[] = {20, 3, 2}

Output : The merged array in sorted order {2, 3, 5, 10, 15, 20}

Input : a[] = {1, 10, 5, 15}

b[] = {20, 0, 2}

Output : The merged array in sorted order {0, 1, 2, 5, 10, 15, 20}

Approach 1

The first approach that can be used here is to concatenate both the arrays and sort the concatenated array. We create a third array of the size of the first two arrays and then transfer all the elements of both the arrays into the resultant array. After the append operation, we sort the resultant array.

C code

  #include   using namespace std;    void sortedMerge(int a[], int b[], int res[],      int n, int m) // Merge two arrays in unsorted manner  {      // Concatenate two arrays      int i = 0, j = 0, k = 0;      while (i < n) { // iterate in first array          res[k] = a[i]; // put each element in res array          i += 1;          k += 1;      }      while (j < m) { // iterate in the second array          res[k] = b[j]; // put each element in res array          j += 1;          k += 1;      }        sort(res, res + n + m); // sort the res array to get the sorted Concatenate  }    int main()  {      int a[] = { 10, 5, 15, 22, 100 };      int b[] = { 20, 3, 2, 12, 1, 7 };      int n = sizeof(a) / sizeof(a[0]); // find the size of array a      int m = sizeof(b) / sizeof(b[0]); // find the size of array b        int res[n + m]; // create res array to Concatenate both the array      sortedMerge(a, b, res, n, m); // call function to append and sort        cout << “The sorted array is: “;      for (int i = 0; i < n + m; i++)          cout << ” ” << res[i];      cout << “n”;        return 0;  }  

Output

The sorted array is:  1 2 3 5 7 10 12 15 20 22 100

Time complexity

O((n+m)log(n+m), where n and m are the sizes of the arrays

Space complexity

O(n+m)

Approach 2

The above approach can be optimised when we use the idea of first sorting then merging it to the third array. Sort both the arrays separately and merge them into the resultant array.

C code

  // CPP program to merge two unsorted lists  // in sorted order  #include   using namespace std;  void sortedMerge(int a[], int b[], int res[],      int n, int m) // Merge two arrays in unsorted manner    {  sort(a, a + n); // Sort the array a   sort(b, b + m); // sort the array b       int i = 0, j = 0, k = 0;  while (i < n && j < m) { // After the array are sorted compare and merge to third array   if (a[i] <= b[j]) { // if element of a is less than b   res[k] = a[i]; // put element of a into the res and increment i   i += 1;  k += 1;  } else {  res[k] = b[j]; // otherwise put the element  of b into the  res array and increment j  j += 1;  k += 1;  }  }  while (i < n) { // If array a elements are left in the array put in res  res[k] = a[i];  i += 1;  k += 1;  }  while (j < m) { // If array a elements are left in the array put in res  res[k] = b[j];  j += 1;  k += 1;  }  }    int main()  {      int a[] = { 10, 5, 15, 22, 100 };      int b[] = { 20, 3, 2, 12, 1, 7 };      int n = sizeof(a) / sizeof(a[0]); // find the size of array a      int m = sizeof(b) / sizeof(b[0]); // find the size of array b        int res[n + m]; // create res array to Concatenate both the array      sortedMerge(a, b, res, n, m); // call function to append and sort        cout << “The sorted array is: “;      for (int i = 0; i < n + m; i++)          cout << ” ” << res[i];      cout << “n”;        return 0;  }  

Output

The sorted array is:  1 2 3 5 7 10 12 15 20 22 100

Time Complexity:

O (nlogn + mlogm + (n + m)) // which is far better than approach 1

Space Complexity:

O ( (n + m) ) It remains same as the approach 1

Next TopicC++ coin change program

C++ program to merge two unsorted arrays

C++ program to merge two unsorted arrays

C++ Program to Convert Decimal to Binary

Default arguments in C++

You may also like