Re: question on merge algorithm

consider :

template<class InIt1, class InIt2, class OutIt>
   OutIt merge(InIt1 first1, InIt1 last1, InIt2 first2, InIt2 last2,
OutIt dest);

Can the destination container already contain some elements ?

If so, will they also be taken into account for doing the sorting and
merging ?

Or, should the destination container have just enough space
to hold the result of the merge( that is, it should not contain any
elements) ?

The reason for asking this question is the following:

#include <cstdlib>
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <iterator>
#include <utility>

using namespace std;

void print(const pair<const int, int>& arg)
{
        cout << arg.first << " " << arg.second << endl;
        return;
}

int main()
{
        typedef pair<int, int> p_type;

        multiset<p_type> c1;

        c1.insert(make_pair(0, 2));
        c1.insert(make_pair(0, 0));
        c1.insert(make_pair(0, 1));
        c1.insert(make_pair(2, 3));

        vector<p_type> c2;

        c2.push_back(make_pair(0, -2));
        c2.push_back(make_pair(1, 2));
        c2.push_back(make_pair(2, 2));

        multimap<int, int> c3;

        c3.insert(make_pair(5, 0));
        c3.insert(make_pair(0, 0));
        c3.insert(make_pair(3, 2));
        c3.insert(make_pair(0, -1));
        c3.insert(make_pair(1, -1));

        merge(c1.begin(), c1.end(), c2.begin(), c2.end(), inserter(c3,
c3.begin()));

        for_each(c3.begin(), c3.end(), print);

        return EXIT_SUCCESS;
}

The output with
g++ -std=c++98 -pedantic -Wall -Wextra x.cpp
is
0 -2
0 0
0 1
0 2
0 0
0 -1
1 -1
1 2
2 2
2 3
3 2
5 0

The second pair (0, 0) in the output should have come before the pair
(0, 1) and
the pair (0, -1) in the output should have come after the pair (0,
-2). Am I correct or wrong ?