C++ recursive function to merge any number of sorted vectorsinto one big sorted vector using divide and
Question:
C++ recursive function to merge any number of sorted vectorsinto one big sorted vector using divide and conquer.
The function is meant to take in a vector of vectors, in whichtheir elements are all sorted in ascending order, and it issupposed to merged those vectors into one big sorted vector.
Here is what the k merge function header looks like: voidKmerge(vector> sortedVecs, int left, int right, vector&res)
- sortedVecs is a vector of vectors where every vector is sortedin ascending order
- left, right are indices
- res is the vector where all the elements will be stored
What I have so far:
void Kmerge(vector> sortedVecs, int left, int right, vector&res){
if(left== right){
return;
}
int middle = (left+right)/2;
Kmerge(sortedVecs, sortedVecs[left], sortedVecs[middle],res);
Kmerge(sortedVecs, sortedVecs[middle+1], sortedVecs[right],res);
}
The approach is similar to merge sort, but here you need todivide the vector of vectors and merge together all of one half toget one big sorted vector, and then all of the other half to getanother sorted vector. You would then merge those two vectors intoone large sorted vector. I've gotten the dividing part down, butnot sure where to go with the merging.
Here's what main looks like:
I already have a merge function that already works which takesin two sorted vectors as arguments, and another vector to hold themerged elements. It merges the vectors by comparing the values ateach index and then inserting them into the res vector in ascendingorder.
Not sure what I would pass into the merge function inside of kmerge, any help is appreciated. Thanks.
Expert Answer:
There is one change in merge function ie for entering the value in the result you must use pushback ... View the full answer
Data Structures and Algorithms in Java
ISBN: 978-1118771334
6th edition
Authors: Michael T. Goodrich, Roberto Tamassia, Michael H. Goldwasser
