//* Variations about merge sort algorithm - different containers

//* C-style arrays *
void MergeSort (const int V1[], int len1, const int V2[], int len2, int S[], int &lens) {

    int i1=0, i2=0;

    // do the merge
    while (i1<len1 && i2<len2) {
        if (V1[i1]<=V2[i2]) 
            S[lens++]=V1[i1++];
        else
            S[lens++]=V2[i2++];
    }

    // finish copying the one remaining array (which one?)
    while (i1<len1) S[lens++]=V1[i1++];
    while (i2<len2) S[lens++]=V2[i2++];
}

//* vector<T> *
void MergeSort (const vector<int> &V1, const vector<int> &V2, vector<int> &S) {

    int i1=0, i2=0;

    S.clear();
    // S.resize(V1.size() + V2.size() ); then use S[x]=... instead of push_back(...);

    // do the merge
    while (i1<V1.size() && i2<V2.size()) {
        if (V1[i1]<=V2[i2]) 
            S.push_back(V1[i1++]);
        else
            S.push_back(V2[i2++]);
    }

    // finish copying the one remaining array (which one?)
    while (i1<len1) S.push_back(V1[i1++]);
    while (i2<len2) S.push_back(V2[i2++]);
}

//* Queue<T> - note a different paradigm  *
void MergeSort (queue<int> &V1, queue<int> &V2, queue<int> &S) {
// Note: if the original queues are not to be destroyed, then pass by value!!

    // Do we really want to clear the queue?
    // - the original program calls for it but typically in queue application
    //   program something else precesses queue elements so we only would add here
    //   as we are processing out elements from V1 and V2

    // do the merge
    while (!V1.empty() && !V2.empty()) {
        if (V1.front()<=V2.front()) {
            S.push(V1.front());
            V1.pop();
        } else {
            S.push(V2.front());
            V2.pop();
        }
    }

    // finish copying the one remaining array (which one?)
    while (!V1.empty()) {
        S.push(V1.front());
        V1.pop();
    }

    while (!V2.empty()) {
        S.push(V2.front());
        V2.pop();
    }
}

//* list<T> *
void MergeSort (const list<int> &V1, const list<int> &V2, list<int> &S) {
// This would also work with vectors, use S.reserve(V1.size()+V2.size()) for efficiency

    S.clear();
    list<int>::const_iterator i = V1.begin();
    list<int>::const_iterator j = V2.begin();

    // do the merge
    while ( i!=V1.end() && j!=V2.end() ) {
        if (*i<=*j) {
            S.push_back(*i);
            ++i;
        } else {
            S.push_back(*j);
            ++j;
        }
    }

    // finish copying the one remaining array (which one?)
    while (i!=V1.end()) {
        S.push_back(*i);
        ++i;
    }

    while (j!=V2.end()) {
        S.push_back(*j);
        ++j;
    }
}

//* list<T> - coding variation with fancy operator notation *
void MergeSort (const list<int> &V1, const list<int> &V2, list<int> &S[]) {
// Note: doing S.push_back(*(i++)); may actually be worse than "two step" procedure
// This would also work with vectors, use S.reserve(V1.size()+V2.size()) for efficiency

    S.clear();
    list<int>::const_iterator i = V1.begin();
    list<int>::const_iterator j = V2.begin();

    // do the merge
    while ( i!=V1.end() && j!=V2.end() ) {
        if (*i<=*j) {
            S.push_back(*(i++));
        } else {
            S.push_back(*(j++));
        }
    }

    // finish copying the one remaining array (which one?)
    while (i!=V1.end()) {
        S.push_back(*(i++));
    }

    while (j!=V2.end()) {
        S.push_back(*(j++));
    }
}

//* processing containers marked with iterators *
temmplate<typename sourceIT, typename destinationIT>
void MergeSort (sourceIT b1, sourceIT e1, sourceIT b2, sourceIT e2, destinationIT bd) {
// Note: Assuming enough space in destination container!
// Note: Use of two kinds of iterators allows to use const_iterator for sources and iterator for destination

    sourceIT i1, i2;
    destinationIT d; // can use bd since it was passed by value

    // do the merge
    while ( i1!=e1 && i2!=e2 ) {
        if (*i1<=*i2) {
            *d = *i1;
            ++i1
            ++d;
        } else {
            *d = *i2;
            ++i2
            ++d;
        }
    }

    // finish copying the one remaining array (which one?)
    while (i1!=e1) {
            *d = *i1;
            ++i1
            ++d;
    }

    while (i2!=e2) {
            *d = *i2;
            ++i2
            ++d;
    }
}