08 MergingFunction.cpp

#include <iostream>

using namespace std;
 
template <class T>
void Print(T& vec, int n, string s){
    cout << s << ": [" << flush;
    for (int i=0; i<n; i++){
        cout << vec[i] << flush;
        if (i < n-1){
            cout << ", " << flush;
        }
    }
    cout << "]" << endl;
}
 
void Merge(int x[], int y[], int z[], int m, int n){
    int i = 0;
    int j = 0;
    int k = 0;
    while (i < m && j < n){
        if (x[i] < y[j]){
            z[k++] = x[i++];
        } else {
            z[k++] = y[j++];
        }
    }
    while (i < m){
        z[k++] = x[i++];
    }
    while (j < n){
        z[k++] = x[j++];
    }
}
 
void MergeSingle(int A[], int low, int mid, int high){
    int i = low;
    int j = mid+1;
    int k = low;
    int B[high+1];
    while (i <= mid && j <= high){
        if (A[i] < A[j]){
            B[k++] = A[i++];
        } else {
            B[k++] = A[j++];
        }
    }
    while (i <= mid){
        B[k++] = A[i++];
    }
    while (j <= high){
        B[k++] = A[j++];
    }
    for (int i=low; i<=high; i++){
        A[i] = B[i];
    }
}
 
int main() {
 
 
    int A[] = {2, 10, 18, 20, 23};
    int m = sizeof(A)/sizeof(A[0]);
    Print(A, m, "\t A");
 
    int B[] = {4, 9, 19, 25};
    int n = sizeof(B)/sizeof(B[0]);
    Print(B, n, "\t B");
 
    int r = m+n;
    int C[r];
    Merge(A, B, C, m, n);
 
    // Print function does not work for variable length array C
    cout << "Sorted" << ": [" << flush;
    for (int i=0; i<r; i++){
        cout << C[i] << flush;
        if (i < r-1){
            cout << ", " << flush;
        }
    }
    cout << "]" << endl;
    cout << endl;
 
    int D[] = {2, 5, 8, 12, 3, 6, 7, 10};
    Print(D, sizeof(D)/sizeof(D[0]), "\t\tD");
    MergeSingle(D, 0, 3, 7);
    Print(D, sizeof(D)/sizeof(D[0]), " Sorted D");
 
 
    return 0;
}