Merging

1. Given two sorted arrays A[m] and B[n], merging is the operation to combine A and B to produce a new sorted array C[m+n].
2. For example, A[] = { 16, 33, 46, 53, 58, 62, 82, 84, 88, 89 }, B[] = { 1, 9, 29, 34, 47, 52, 54, 66, 95, 98 }. Merging A[] and B[] will produce C[] = { 1, 9, 16, 29, 33, 34, 46, 47, 52, 53, 54, 58, 62, 66, 82, 84, 88, 89, 95, 98 }.
3. Write a program which
   1. Read K positive integers from the input. Store them in array A in ascending order.
   2. Read K positive integers from the input. Store them in array B in ascending order.
   3. Merge array A and array B and save the result in array C. Note the size of C should be 2K.
   4. Print out elements in array C, to verify that they are arranged in ascending order.
4. For a small value of K (e.g., K=4), the output of the program may look as below:

   
   Array A Sorted:
   1
   4
   5
   7
   Array B Sorted:
   2
   3
   6
   9
   Merged as Array C:
   1
   2
   3
   4
   5
   6
   7
   9
   
   

5. An intuitive way to do this is to concatenate A and B arbitrarily, and then sort the new array. You can develop a program by doing so, and measure how long it takes to merge A and B when K = 100000. Note that only Step 3 mentioned above, which is the line shown in purple, need to be measured.)
6. Because both A and B are sorted, you can have a more efficient solution according to the following algorithm:
   
7. Measure how long it takes this algorithm to merge two arrays of size K = 100000, and compare it with your previous version.
8. Submit your program implementing this merging algorithm. The robot will supply test input with K = 100000. That is, your program should expect to read 200000 integers from the input.
9. Q: How do I prepare an input with 2K integers? Of course it is impossible to type this from keyboard manually.
   A: You can write a small C++ program which prints out 2K random integers:

   
   #include <iostream>
   using std::cout;
   using std::endl;
   
   int main()
   {
       const int K = 100000;
       srand( time(NULL) );
       for (int i=0; i<2*K; i++)
           cout << rand() << endl;
       return 0;
   }
   
   

   Running the executable binary file will output 2K random integers to the screen. If you want to save them in a file, you may type the command "a.out > input.1", which saves the output in a file. Then in your next step you may type the command "merge.exe < input.1" to read the input from this file.
10. For more information, try to search the Internet to learn about Unix Input and Output Redirection