Is There an Alternative to insert and then sort

Question

If I have vector<int> foo and vector<int> bar both of which are sorted, and I want to merge them into foo such that the final result is sorted, does the standard provide me a method for doing this?

Obviously I can do:

foo.insert(foo.end(), bar.begin(), bar.end());
sort(foo.begin(), foo.end());

But I was hoping there was a one step algorithm to accomplish this.

Answer 1

It might be faster to use std::inplace_merge instead of std::sort. If there is additional memory available it has linear complexity otherwise it falls back to NlogN.

auto middle = foo.insert(foo.end(), bar.begin(), bar.end());
std::inplace_merge(foo.begin(), middle, foo.end());