X-Git-Url: https://git.sesse.net/?p=stockfish;a=blobdiff_plain;f=src%2Fmovepick.cpp;h=5c8338c0c19ab96d08f55879015d8f422002985c;hp=72601bb3b3f23c4909e9bdf602d21b8a95ba440a;hb=733d0099b2a3e3ad594bb551d37c8a06c62f13db;hpb=b8c5ea869ca80338f8b2fa6815fc92349b889750

diff --git a/src/movepick.cpp b/src/movepick.cpp
index 72601bb3..5c8338c0 100644
--- a/src/movepick.cpp
+++ b/src/movepick.cpp
@@ -35,6 +35,20 @@ namespace {
     STOP
   };
 
+  // Our insertion sort, guaranteed to be stable, as is needed
+  void insertion_sort(MoveStack* begin, MoveStack* end)
+  {
+    MoveStack tmp, *p, *q;
+
+    for (p = begin + 1; p < end; ++p)
+    {
+        tmp = *p;
+        for (q = p; q != begin && *(q-1) < tmp; --q)
+            *q = *(q-1);
+        *q = tmp;
+    }
+  }
+
   // Unary predicate used by std::partition to split positive scores from remaining
   // ones so to sort separately the two sets, and with the second sort delayed.
   inline bool has_positive_score(const MoveStack& ms) { return ms.score > 0; }
@@ -230,14 +244,14 @@ void MovePicker::generate_next() {
       endQuiets = end = generate<QUIETS>(pos, moves);
       score<QUIETS>();
       end = std::partition(cur, end, has_positive_score);
-      sort<MoveStack>(cur, end);
+      insertion_sort(cur, end);
       return;
 
   case QUIETS_2_S1:
       cur = end;
       end = endQuiets;
       if (depth >= 3 * ONE_PLY)
-          sort<MoveStack>(cur, end);
+          insertion_sort(cur, end);
       return;
 
   case BAD_CAPTURES_S1: