question on merge algorithm

[subramanian100in]

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, intp_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_typec2 ;

c2.push_back(ma ke_pair(0, -2));
c2.push_back(ma ke_pair(1, 2));
c2.push_back(ma ke_pair(2, 2));

multimap<int, intc3;

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.beg in(), 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 ?

Kindly clarify.

Thanks
V.Subramanian