> For the complete documentation index, see [llms.txt](https://maksimdan.gitbook.io/interview-practice-problems/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://maksimdan.gitbook.io/interview-practice-problems/coding_practice_questions/interview_questions_4/sorted-merge.md).

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