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);
}