diff --git a/cpp/graph.hpp b/cpp/graph.hpp
index 987d9a89ddf802d397f3af178816d475e21f92ec..976589eda84764818941fa30e876f41fdf9fe8c2 100644
--- a/cpp/graph.hpp
+++ b/cpp/graph.hpp
@@ -30,6 +30,30 @@ class DiDegree {
 typedef std::vector<unsigned int> DegreeSequence;
 typedef std::vector<DiDegree> DiDegreeSequence;
 
+template< class RandomIt, class Compare >
+void insertionSort( RandomIt first, RandomIt last, Compare comp ) {
+    for (RandomIt next = first;;) {
+        RandomIt a = next;
+        next++;
+        if (next == last)
+            break;
+        RandomIt b = next;
+        auto newvalue = *next;
+        //                next
+        // 1 2 3 4  5  6   4
+        //             a   b
+        //          a  b
+        //       a  b
+        // a b
+        while (b != first && comp(newvalue, *a)) { // if newvalue < *a
+            *b = *a;
+            a--;
+            b--;
+        }
+        *b = newvalue;
+    }
+}
+
 class Graph {
   public:
     Graph() {}
@@ -79,12 +103,10 @@ class Graph {
         reset(n);
 
         while (!degrees.empty()) {
-            // Construction will find maximum triangles only if sort is stable
-            // and does NOT sort on vertex id
-            std::stable_sort(degrees.begin(), degrees.end(),
-                             [](const auto &p1, const auto &p2) {
-                                 return p1.first < p2.first;
-                             });
+            insertionSort(degrees.begin(), degrees.end(),
+                          [](const auto& p1, const auto& p2) {
+                              return p1.first < p2.first;
+                          });
             // Highest degree is at back of the vector
             // Take it out
             unsigned int degree = degrees.back().first;