`std::sort` does not perserve the order of elements within equal values, however the result of it is of no randomness.

stability_test_of_std_sort.cc

#include <iostream>                                                                                                                                                    
#include <algorithm>                                                                                    
#include <vector> 
#include <utility>
#include <random>

namespace {
const constexpr size_t kTestLen = 1000000;
std::random_device rd;
std::mt19937 urbg(rd());
using FirstT  = size_t;
using SecondT = size_t;
using PairT   = std::pair<FirstT, SecondT>;
}  // namespace

namespace std {
template <> struct less<PairT> {
  inline constexpr bool operator()(const PairT& lhs, const PairT& rhs) const {
    return lhs.first < rhs.first;
  }
};
}  // namespace std

int main() {
  std::vector<PairT> round_one;
  round_one.reserve(kTestLen);
  for (size_t i = 0; i != kTestLen; ++i) {
    round_one.emplace_back(i / 3, i);
  }

  std::shuffle(round_one.begin(), round_one.end(), urbg);
  std::vector<PairT> round_two(round_one);

  std::less<PairT> pair_less;
  std::sort(round_one.begin(), round_one.end(), pair_less);
  std::sort(round_two.begin(), round_two.end(), pair_less);

  std::cout << (round_one == round_two) << std::endl;
  return 0;
}

Compile and execute by:

g++ -std=c++11 -O3 stability_test_of_std_sort.cc -o stability_test_of_std_sort
./stability_test_of_std_sort