MERGING - SOLUTION

#include <iostream>

using namespace std;


int main()
{
int m,n,k;
cin>>m;
int A[m];
for(int i=0;i<m;i++){
cin>>A[i];
    }
cin>>n;
int B[n];
    k=m+n;
int C[k];
for(int i=0;i<n;i++){
cin>>B[i];
    }
for(int i=0,p=0;i<m+n;i++){
if(i<m){
            C[i]=A[i];
        }
else{
            C[i]=B[p++];
        }
    }
/*  for(int i=0;i<k;i++){
        cout<<C[i]<<endl;;
    }*/
    int j;
for(int i=1;i<k;i++){
int b=C[i];
for(j=i-1;j>=0;j--){
if(C[j]>b){
                C[j+1]=C[j];
            }
else{
break;
            }
        }
        C[j+1]=b;
    }
//  cout<<"Sortiran:"<<endl;
for(int i=0;i<k;i++){
cout<<C[i]<<endl;
    }
return 0;
}

Task description

The task is to merge two sorted arrays of numbers into one, which must also be sorted. This is a common problem of merging sorted arrays.
​

Explanation of the code

cin >> m;
int A[m];
for (int i = 0; i < m; i++) {
cin >> A[i];
}
cin >> n;
int B[n];
for (int i = 0; i < n; i++) {
cin >> B[i];
}
Here two arrays A and B are entered, with m and n elements respectively. Each array is already sorted.

Combining and sorting

​The program combines arrays A and B into one array C:
int k = m + n;
int C[k];
for (int i = 0; i < m; i++) {
C[i] = A[i];
}
for (int i = 0, p = 0; i < n; i++) {
C[m + i] = B[i];
}

​Then array C is sorted with insertion sort:
int j;
for (int i = 1; i < k; i++) {
int b = C[i];
for (j = i - 1; j >= 0 && C[j] > b; j--) {
C[j + 1] = C[j];
}
C[j + 1] = b;
}

​Printing the result:
for (int i = 0; i < k; i++) {
cout << C[i] << endl;
}

A comment on the code

​
The code is almost correct, but there is a weakness in how the arrays are combined. The “merging sorted lists” method should be used instead of sorting the whole array after combining, because the input arrays are already sorted.
​
Optimization:
Since the input arrays are already sorted, you can use a more efficient merging algorithm, which is O(m + n), instead of the O((m + n)²) used in the current code. This can be done using two pointers to go through arrays A and B.

Optimized code

#include < iostream >
using namespace std;

int main() {
int m, n;
cin >> m;
int A[m];
for (int i = 0; i < m; i++) {
cin >> A[i];
}
cin >> n;
int B[n];
for (int i = 0; i < n; i++) {
cin >> B[i];
}

int i = 0, j = 0;
while (i < m && j < n) {
if (A[i] <= B[j]) {
cout << A[i++] << endl;
} else {
cout << B[j++] << endl;
}
}

while (i < m) {
cout << A[i++] << endl;
}

while (j < n) {
cout << B[j++] << endl;
}

return 0;
}

Explanation of the optimized code

  1. Initialization and input: Entering the data is the same as in the first code.
  2. Merging and printing:
    • We use two pointers i and j to go through arrays A and B.
    • We compare the current elements and print the smaller one, until one of the arrays is used up.
    • After that, we print the remaining elements from the remaining arrays.
This optimized code is much faster because it has O(m + n) complexity, which is better than O((m + n)²).