# 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 updated