using namespace std;
#include <iostream>
#include <vector>
// combine two sorted lists A and B into R
// displays comparison every time it is done
void combine( const vector< int > & A, const vector< int > & B, vector< int > & R)
{
auto itA = A.begin ( ) ;
auto itB = B.begin ( ) ;
while ( ( itA ! = A.end ( ) ) && ( itB ! = B.end ( ) ) )
{
if ( * itA < * itB)
{
R.push_back ( * itA) ;
itA++ ;
}
else
{
R.push_back ( * itB) ;
itB++ ;
}
}
while ( itA ! = A.end ( ) )
{
R.push_back ( * itA) ;
itA++ ;
}
while ( itB ! = B.end ( ) )
{
R.push_back ( * itB) ;
itB++ ;
}
cout << "comparison" << endl;
// be careful -- R comes in as an empty vector
}
int main( )
{
vector< int > L1;
vector< int > L2;
vector< int > L3;
int N; // how many elements in each of L1 and L2
int e; // for each element
cout << "How many elements in each list?" << endl;
cin >> N;
cout << "List1" << endl;
for ( int i = 0 ; i < N; i++ )
{
cout << "element :" << endl; cin >> e; L1.push_back ( e) ;
}
cout << endl << "List2" << endl;
for ( int i = 0 ; i < N; i++ )
{
cout << "element :" << endl; cin >> e; L2.push_back ( e) ;
}
combine( L1, L2, L3) ;
cout << "The result is: " ;
for ( int i = 0 ; i < N * 2 ; i++ )
{
cout << L3[ i] << " | " ;
} cout << endl;
} // end of main
dXNpbmcgbmFtZXNwYWNlIHN0ZDsKI2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8dmVjdG9yPgoKCi8vIGNvbWJpbmUgdHdvIHNvcnRlZCBsaXN0cyBBIGFuZCBCIGludG8gUgovLyBkaXNwbGF5cyBjb21wYXJpc29uIGV2ZXJ5IHRpbWUgaXQgaXMgZG9uZQp2b2lkIGNvbWJpbmUoY29uc3QgdmVjdG9yPGludD4mIEEsIGNvbnN0IHZlY3RvcjxpbnQ+JiBCLCB2ZWN0b3I8aW50PiYgUikKewogICAgYXV0byBpdEEgPSBBLmJlZ2luKCk7CiAgICBhdXRvIGl0QiA9IEIuYmVnaW4oKTsKCiAgICB3aGlsZSAoIChpdEEgIT0gQS5lbmQoKSkgJiYgKGl0QiAhPSBCLmVuZCgpKSApCgl7CiAgICAgICAgaWYgKCppdEEgPCAqaXRCKSAKCQl7CiAgICAgICAgICAgIFIucHVzaF9iYWNrKCppdEEpOwoJCQlpdEErKzsKICAgICAgICB9CiAgICAgICAgZWxzZSAKCQl7CiAgICAgICAgICAgIFIucHVzaF9iYWNrKCppdEIpOwoJCQlpdEIrKzsKICAgICAgICB9CiAgICB9Cgl3aGlsZShpdEEgIT0gQS5lbmQoKSkKCXsKCQlSLnB1c2hfYmFjaygqaXRBKTsKCQlpdEErKzsKCX0KCXdoaWxlKGl0QiAhPSBCLmVuZCgpKQoJewoJCVIucHVzaF9iYWNrKCppdEIpOwoJCWl0QisrOwoJfQoJY291dCA8PCAiY29tcGFyaXNvbiIgPDwgZW5kbDsKCS8vIGJlIGNhcmVmdWwgLS0gUiBjb21lcyBpbiBhcyBhbiBlbXB0eSB2ZWN0b3IKfQoKCmludCBtYWluKCkKewogICAgdmVjdG9yPGludD4gTDE7CiAgICB2ZWN0b3I8aW50PiBMMjsKICAgIHZlY3RvcjxpbnQ+IEwzOwogICAgaW50IE47ICAvLyBob3cgbWFueSBlbGVtZW50cyBpbiBlYWNoIG9mIEwxIGFuZCBMMgogICAgaW50IGU7ICAvLyBmb3IgZWFjaCBlbGVtZW50CgogICAgY291dCA8PCAiSG93IG1hbnkgZWxlbWVudHMgaW4gZWFjaCBsaXN0PyIgPDwgZW5kbDsKICAgIGNpbiA+PiBOOwoKICAgIGNvdXQgPDwgIkxpc3QxIiA8PCBlbmRsOwogICAgZm9yIChpbnQgaSA9IDA7IGkgPCBOOyBpKyspCiAgICB7CiAgICAJY291dCA8PCAiZWxlbWVudCA6Ijw8ZW5kbDsgY2luID4+IGU7IEwxLnB1c2hfYmFjayhlKTsKICAgIH0KCiAgICBjb3V0IDw8IGVuZGwgPDwgIkxpc3QyIiA8PCBlbmRsOwogICAgZm9yIChpbnQgaSA9IDA7IGkgPCBOOyBpKyspCiAgICB7CiAgICAJY291dCA8PCAiZWxlbWVudCA6Ijw8ZW5kbDsgY2luID4+IGU7IEwyLnB1c2hfYmFjayhlKTsKICAgIH0KCiAgICBjb21iaW5lKEwxLCBMMiwgTDMpOwoKCiAgICBjb3V0IDw8ICJUaGUgcmVzdWx0IGlzOiAiOwogICAgZm9yIChpbnQgaSA9IDA7IGkgPCBOICogMjsgaSsrKQogICAgewogICAgICAgIGNvdXQgPDwgTDNbaV08PCIgfCAiOwogICAgfSBjb3V0IDw8IGVuZGw7Cgp9Ly8gZW5kIG9mIG1haW4=