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:
    Merge
  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