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

To elaborate on Mat's comment your code could look like this using std::merge:

std::vector<int> result;
std::merge(
    foo.begin(), foo.end(),
    bar.begin(), bar.end(),
    std::back_inserter(result));

foo = result; // if desired

Answer 2

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

Answer 3

If you need this kind of merge, why not make one yourself?

template <class Vector>
void insert_sorted(Vector& where, Vector& what)
{
    typename Container::iterator src = what.begin();
    typename Container::iterator src_end = what.end();

    size_t index = 0;

    while(src != src_end)
    {
        if(*src < where[index])
        {
            where.insert(where.begin() + index, *src);
            ++src;
        }

        ++index;
    }
}

Sample usage:

vector<int> foo{ 0, 5, 7, 9, 11, 14 };
vector<int> bar{ 1, 2, 4, 8, 10, 12 };

insert_sorted(foo, bar);

for(vector<int>::iterator i = foo.begin(); i != foo.end(); ++i)
    cout << *i << " ";

Output:

0 1 2 4 5 7 8 9 10 11 12 14

Live sample: link.

Answer 4

So after looking through all the standard algorithms I can confirm that, there is no alternative to insert and sort. As I was searching the standard algorithms I did note that all the copying algorithms use input iterators and output iterators the only time an input-output iterators are used is when a single range is being operated on. (For example sort uses input-output iterators but any copy uses input iterators and an output iterator.)

I'd like to give an illustration of my point. So lets make an example of what an insertion merge algorithm with an input-output iterator would look like:

template <class BidirectionalIterator, class InputIterator>
void func(BidirectionalIterator first1, BidirectionalIterator last1, InputIterator first2, InputIterator last2){
    bool is1Empty = first1 == last1;
    bool is2Empty = first2 == last2;
    BidirectionalIterator end = next(last1, distance(first2, last2));

    if (!is1Empty){
        --last1;
    }

    if (!is2Empty){
        --last2;
    }

    while (!is1Empty || !is2Empty){
        --end;
        if (!is1Empty){
            if (!is2Empty && *last2 > *last1){
                *end = *last2;

                if (last2 == first2){
                    is2Empty = true;
                }else{
                    --last2;
                }
            }else{
                *end = *last1;

                if (last1 == first1){
                    is1Empty = true;
                }
                else{
                    --last1;
                }
            }
        }else{
            *end = *last2;

            if (last2 == first2){
                is2Empty = true;
            }
            else{
                --last2;
            }
        }
    }
}

Two things should be noted about this func algorithm:

1. It doesn't respect last1 it is assumed that sufficient space is allocated beyond last1 to also contain all the elements in the input range
2. func's input-output range cannot be called with a back_inserter like any other output only range in a standard algorithm

Because of this even func cannot be a "one step algorithm". It must be called like this:

 foo.resize(foo.size() + bar.size());
 func(foo.begin(), next(foo.begin(), foo.size() - bar.size()), bar.begin(), bar.end());

Note that Blastfurnace's answer takes advantage of the knowledge that it is merging two sorted ranges, and as such is of equivalent speed to func:

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

The only actual "one step algorithm" is to roll this Blastfurnace's answer into a function that you could call by passing in the containers to be merged.