diff --git a/cpp/graph_ccm.hpp b/cpp/graph_ccm.hpp
index 722389df1d432543e97ffd4c026d8af4b2fabd5d..381d2040dcdc6a751f784c5823ca8171917d8ece 100644
--- a/cpp/graph_ccm.hpp
+++ b/cpp/graph_ccm.hpp
@@ -23,6 +23,13 @@ bool constrainedConfigurationModel(DegreeSequence &ds, Graph &g, RNG &rng,
         degrees[i].second = i;
     }
 
+    // This should make the random pairing faster
+    // More likely to pair up with something at the end of an array
+    // So erasing that element from the array then requires less moves
+    std::sort(
+            degrees.begin(), degrees.end(),
+            [](const auto &p1, const auto &p2) { return p1.first < p2.first; });
+
     // remaining half-edges , iterator into `degrees`
     std::vector<std::pair<unsigned int, decltype(degrees.begin())>> available;
     available.reserve(n);
@@ -76,13 +83,16 @@ bool constrainedConfigurationModel(DegreeSequence &ds, Graph &g, RNG &rng,
                 unsigned int halfEdge = distr(rng);
                 unsigned int cumulative = 0;
                 auto vIter = uIter;
-                for (auto iter = available.begin(); iter != available.end();
+                // Reverse has higher probability to be fast because high
+                // degrees are near the end
+                for (auto iter = available.rbegin(); iter != available.rend();
                      ++iter) {
                     cumulative += iter->first;
                     if (halfEdge <= cumulative) {
                         vIter = iter->second;
                         availableEdges -= iter->first;
-                        available.erase(iter);
+                        // Reverse iterators are tricky
+                        available.erase(std::next(iter).base());
                         break;
                     }
                 }
@@ -107,7 +117,9 @@ bool constrainedConfigurationModel(DegreeSequence &ds, Graph &g, RNG &rng,
             auto vIter = uIter;
             unsigned int halfEdge = distr(rng);
             unsigned int cumulative = 0;
-            for (auto iter = available.begin(); iter != available.end();
+            // Reverse has higher probability to be fast because high degrees
+            // are near the end
+            for (auto iter = available.rbegin(); iter != available.rend();
                  ++iter) {
                 cumulative += iter->first;
                 if (halfEdge <= cumulative) {