Overview: STL vectors can grow and shrink dynamically and the member functions of the STL vector class can help us more conveniently handle the dynamic nature of memory allocation. A STL vector also maintains the information of its size (the number of elements currently in it) dynamically and so we don't need separate variables or parameters to record the sizes of vectors. You can just call the size() member function from a vector to know the current size of the vector The program should work in a way 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 #include using namespace std, bool mergeTwoSortedVectors vector & vecA, vector & vecB, vector & vecC) /Your code void mergeSort(vector & vecToSort) //Your code int main( //Your code Step 1: Implement the mergeTwoSortedVectors function Given (references to) two vector 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 & vecA, vector & vecB, vector & 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 vecC before any merging operations to make sure vecC is of the right size to store all the values in vecA and vecB 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 ofelements 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 2. Pick the smaller of the two values, merge it into vecC by copying it into 3. merge in vecB (i.e. vecBfcountB]) the vecC[countC] in vecC. 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 nl or n2 in the input: Declare three separate vector vectors. Ask the user to enter two non-negative integers nl and n2. Resize those three vectors to the sizes of nl, n2, and (nl+n2) respectively Then use a loop to ask the user to enter a series of nl sorted values and store them in the vector (of size nl). 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 (nl+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 function Implement the following recursive merge sort function by using the mergeTwoSortedSeries function implemented in Step 1 void mergeSort vector & 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 vecl 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 mergeSortvecl) to sort the first vector . Call mergeSort(vec2) to sort the second vector . Call mergeIwoSortedVectors(vec vec2, vecToSort) to merge the twosorted vectors vecl and vec2 into vecToSort to make it a sorted vector Step 4: Test the implementation of the mergeSort functioin 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 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, the problem is finished Overview: STL vectors can grow and shrink dynamically and the member functions of the STL vector class can help us more conveniently handle the dynamic nature of memory allocation. A STL vector also maintains the information of its size (the number of elements currently in it) dynamically and so we don't need separate variables or parameters to record the sizes of vectors. You can just call the size() member function from a vector to know the current size of the vector The program should work in a way 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 #include using namespace std, bool mergeTwoSortedVectors vector & vecA, vector & vecB, vector & vecC) /Your code void mergeSort(vector & vecToSort) //Your code int main( //Your code Step 1: Implement the mergeTwoSortedVectors function Given (references to) two vector 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 & vecA, vector & vecB, vector & 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 vecC before any merging operations to make sure vecC is of the right size to store all the values in vecA and vecB 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 ofelements 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 2. Pick the smaller of the two values, merge it into vecC by copying it into 3. merge in vecB (i.e. vecBfcountB]) the vecC[countC] in vecC. 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 nl or n2 in the input: Declare three separate vector vectors. Ask the user to enter two non-negative integers nl and n2. Resize those three vectors to the sizes of nl, n2, and (nl+n2) respectively Then use a loop to ask the user to enter a series of nl sorted values and store them in the vector (of size nl). 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 (nl+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 function Implement the following recursive merge sort function by using the mergeTwoSortedSeries function implemented in Step 1 void mergeSort vector & 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 vecl 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 mergeSortvecl) to sort the first vector . Call mergeSort(vec2) to sort the second vector . Call mergeIwoSortedVectors(vec vec2, vecToSort) to merge the twosorted vectors vecl and vec2 into vecToSort to make it a sorted vector Step 4: Test the implementation of the mergeSort functioin 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 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, the problem is finished