Purpose: Get used to the
concept of object-oriented programming by using vector objects of the powerful

**Overview**: *the size(
)*

**Sample Executable: **Your program should work like the demo executable here, which allows the user to (i) provide and
merge numbers in two sorted vectors into a single sorted vector and (ii)
provide and sort the numbers in a vector.

**Structure of your program**: You only need a single cpp file for this assignment
and the structure should looks like the following:

*#include <iostream>*

*#include <vector>*

*using
namespace std;*

*bool
mergeTwoSortedVectors*

*(vector<double>
& vecA, vector<double> & vecB, vector<double> & vecC)*

*{
*

*//Your code*

*}*

*void
mergeSort(vector<double> & vecToSort)*

*{
*

*//Your code*

*}*

*int
main( )*

*{*

*//Your code*

*}*

**Step 1: Implement the ***mergeTwoSortedVectors *

Given
(references to) two *vector<double> *vectors* vecA *and *vecB*, each of which* *contains values already sorted in
ascending order, implement the following function that can merge the values
stored in these two separate sorted vector into a single vector *vecC* with all the values in it sorted in
ascending order.

*bool
mergeTwoSortedVectors*

*(vector<double>
& vecA, vector<double> & vecB, vector<double> & vecC)*

*{*

*//Your code*

*}*

**Checking the
precondition:**

The
values stored in *vecA* and those in *vecB* must be in ascending order already.
Your implementation should check to make sure they are already sorted, and if
they are not both sorted, stop and return *false*.
(The *mergeTwoSortedVectors* function should check this.). You should also
invoke the ** resize( ) member function** from

**Implementation of the merge operations**:

For
vector *vecA*, use a separate integer
variable *countA* to keep the count of
the number of elements in vector *vecA*
(starting from the beginning of the vector *vecA*)
already merged into the vector *vecC*.
Do the same thing with an integer variable *countB*
for vector *vecB* to keep the count of
the number of elements in vector *vecB*
(starting from the beginning of the vector *vecB*)
already merged into the vector *vecC*.
For vector *vecC*, keep an integer
variable *countC* as the count of the
number of elements already merged (from both *vecA* and *vecB*) into *vecC*. Initially all three counts are
simply 0.

**Essentially you need to implement three
separate loops below**:

**Loop 1**: Repeatedly do the following as long as *vecA* and *vecB* **both **still have elements not yet merged
into *vecC*:

1. Compare the next element to merge in *vecA *(i.e. *vecA[countA])* with* *the
next element to merge in *vecB *(i.e. *vecB[countB])* .

2. Pick the smaller of the two values, merge it into *vecC* by copying it into the *vecC[countC]
*in *vecC*.

3. Update the counts in *countA*, *countB*, and *countC *accordingly.

Note
that after Loop 1 is finished, the elements in one of the two vectors (*vecA* or *vecB)* must have been completely merged into *vecC *by this time.* *We
need to copy whatever the remaining elements in *vecA* or *vecB* into *vecC *using the following two loops.
(Note that exactly only one of Loop 2 and Loop 3 below will encounter any
remaining elements needed to be copied into *vecC*.)

**Loop 2**: Use a loop to copy all the remaining elements left in *vecA* into *vecC *one by one.

**Loop 3**: Use a loop to copy the remaining elements left in *vecB* into *vecC *one by one.

**After Loop 3, return true**

**Step 2**: **Test the implementation of the
***mergeTwoSortedVectors ***function**

Create
a loop in your main function to repeatedly do the following test on the *mergeTwoSortedVectors
*function until the user enters a
negative value for *n1 *or* n2* in the input:

· Declare three separate *vector<double>* vectors. Ask the user to enter two
non-negative integers *n1* and *n2*. Resize those three vectors to the
sizes of *n1*, *n2*, and (*n1+n2*)
respectively. Then use a loop to ask the user to enter a series of *n1* sorted values and store them in the
vector (of size *n1*). Similarly use a
loop to ask the user to enter a series of *n2*
sorted values and store them in the vector (of size *n2*). Then call the *mergeTwoSortedVectors *function appropriately to merge the two
series of sorted values in the first two vectors into the one sorted series of
values stored in the third vector. Output the contents of the (*n1+n2*)
element in the third vector to verify that the two sorted series stored
in the first two vectors have been correctly merged into a sorted series stored in the third vector.

**You have to make sure that mergeTwoSortedVectors
is working perfectly (by doing extensive testing in Step 2) before you
proceed to Step 3 below.**

**If you are 100% sure your mergeTwoSortedVectors
is working, you can comment out the testing code in the main function when
you proceed to Step 3 below.**

**Step 3:** **Implement the ***mergeSort *

Implement
the following recursive merge sort function by using the *mergeTwoSortedSeries
*function implemented in Step 1.

*void
mergeSort(vector<double> & vecToSort)*

*{*

*//Your code*

*}*

· If the size of *vecToSort *is 1 or less, it is already sorted just return.

· If the size
of *vecToSort * is 2, compare the two elements in it and swap
them if necessary, and then return.

· Otherwise, the
size of *vecToSort * is at
least 3. In this case, we should use two separate vectors *vec1 *and *vec2* (as local
objects), resize them to the sizes *vecToSort.size( )/2 *and
*vecToSort.size( ) -
vecToSort.size( )/2* respectively,*
*and copy the first *vecToSort.size( )/2 *elements in *vecToSort* into the first
vector and the remaining *vecToSort.size(
) - vecToSort.size( )/2* into the second vector.

· Call *mergeSort(vec1) * to sort the first vector.

· Call *mergeSort(vec2) *to sort the second vector.

· Call *mergeTwoSortedVectors(vec1, vec2, vecToSort) * to
merge the two sorted vectors *vec1 *and
*vec2 *into *vecToSort* to make it a sorted vector

**Step 4**: **Test the implementation of the
***mergeSort ***function**

Create
a loop in your main function to repeatedly do the following test on the *mergeSort
*function until the user enters a
negative value for *n* in the input:

· Declare a *vector<double>*
vector. Ask the user to enter one non-negative integer *n*. Resize the vector to the size of *n*. Use a loop to ask the user to enter a series of *n* sorted values and store them in the
vector of size *n*. Then call the *mergeSort
*function appropriately to sort the
vector. Output the contents of this final sorted series to verify the
result.

**When you are sure mergeSort
is working perfectly, you are done. **