Why does std::sort appears to alternate the values in the vector

The below code snippet shows that std::sort is alternating the values in the vector which is quite confusing.

std::vector<int> a;
std::vector<std::string> b;
std::vector<std::pair<int&, std::string&>> p;

a.push_back(1);
a.push_back(3);
a.push_back(2);
b.push_back("hi 1");
b.push_back("hi 3");
b.push_back("hi 2");

p.push_back(std::pair<int&, std::string&>(a[0],b[0]));
p.push_back(std::pair<int&, std::string&>(a[1],b[1]));
p.push_back(std::pair<int&, std::string&>(a[2],b[2]));

std::sort(p.begin(),p.end());

std::cout << a[0] << " " << a[1] << " " << a[2] <<  std::endl;
std::cout << b[0] << " " << b[1] << " " << b[2] <<  std::endl;

I am expecting it to print

1 2 3
hi 1 hi 2 hi 3

but instead it prints

1 3 3
hi 1 hi 3 hi 3

Why? My compiler is gcc 4.9.3.

I am trying to sort two vectors together and using vector of pairs of references is suggested in http://stackoverflow.com/a/37929675/3667089.