Sorted Merge
10.1 Sorted Merge: You are given two sorted arrays, A and B, where A has a large enough buffer at the end to hold B. Write a method to merge B into A in sorted order.
- Order 2n, with O(n) extra space```c++ void sorted_merge(vector &one, vector &two) { int iter1 = 0, iter2 = 0; int count = 0; vector temp(one.size()); while (one.at(iter1) != 0 && (iter1 < one.size() || iter2 < two.size())) { if (one.at(iter1) < two.at(iter2)) temp.at(count++) = one.at(iter1++);else if (one.at(iter1) >= two.at(iter2))temp.at(count++) = two.at(iter2++);}while (one.at(iter1) != 0 && iter1 < one.size()) temp.at(count++) = one.at(iter1++); while (iter2 < two.size()) temp.at(count++) = two.at(iter2++);for (int i = 0; i < temp.size(); i++) one.at(i) = temp.at(i); }
int main() { vector one = { 1,2,3,4 }; one.resize(10); vector two = { -1,2,3,10,6,20 };
sorted_merge(one, two);
print(one);
}
* O(N) time, O(1) Space, best as we can get
* Simpler too. We just decrement from the end, and look for the greatest elements.
```c++
void sorted_merge(vector<int> &one, vector<int> &two) {
if (two.empty()) return;
// find one end position
int iter1, iter2 = two.size() - 1;
for (int i = 0; i < one.size(); i++) {
if (one.at(i) == 0) {
iter1 = i - 1;
break;
}
}
int count = one.size() - 1;
while (iter1 >= 0 && iter1 >= 0) {
if (one.at(iter1) > two.at(iter2))
one.at(count--) = one.at(iter1--);
else if (one.at(iter1) <= two.at(iter2))
one.at(count--) = two.at(iter2--);
}
while (iter1 >= 0) one.at(count--) = one.at(iter1--);
while (iter2 >= 0) one.at(count--) = two.at(iter2--);
}
int main()
{
vector<int> one = { -3 ,-1, 4, 10 };
one.resize(8);
vector<int> two = { -10, 5,6,7 };
sorted_merge(one, two);
print(one);
one = { 1,2,3,4 };
one.resize(10);
two = { -1,2,3,10,20,30 };
sorted_merge(one, two);
print(one);
}
Last modified 3yr ago