From 4dd7fccfd18a809cf1e3b589c2ec77f4b386dad6 Mon Sep 17 00:00:00 2001
From: Marco Costalba <mcostalba@gmail.com>
Date: Thu, 15 Oct 2009 13:08:39 +0200
Subject: [PATCH] Use an homegrown insertion sort instead of std::sort()

It is stable and it is also a bit faster then std::sort()
on the tipical small move lists that we need to handle.

Verified to have same functionality of std::stable_sort()

After 999 games at 1+0
Mod vs Orig +240 =534 -225 50.75%  507.0/999  +5 ELO

Signed-off-by: Marco Costalba <mcostalba@gmail.com>
---
 src/move.h       | 22 +++++++++++++++++++++-
 src/movepick.cpp | 11 +++++------
 2 files changed, 26 insertions(+), 7 deletions(-)

diff --git a/src/move.h b/src/move.h
index 672eade6..2ba08840 100644
--- a/src/move.h
+++ b/src/move.h
@@ -62,9 +62,29 @@ struct MoveStack {
   int score;
 };
 
-// Note that operator< is set up such that std::sort() will sort in descending order
+// Note that operator< is set up such that sorting will be in descending order
 inline bool operator<(const MoveStack& f, const MoveStack& s) { return s.score < f.score; }
 
+// Our stable insertion sort in range [firstMove, lastMove), platform independent
+template<typename T>
+inline void sort_moves(T* firstMove, T* lastMove)
+{
+    T value;
+    T *cur, *p, *d;
+
+    if (firstMove != lastMove)
+        for (cur = firstMove; ++cur != lastMove; )
+        {
+            p = d = cur;
+            value = *p--;
+            if (value < *p)
+            {
+                do *d = *p;
+                while (--d != firstMove && value < *--p);
+                *d = value;
+            }
+        }
+}
 
 ////
 //// Inline functions
diff --git a/src/movepick.cpp b/src/movepick.cpp
index ea435026..34cb642b 100644
--- a/src/movepick.cpp
+++ b/src/movepick.cpp
@@ -23,7 +23,6 @@
 //// Includes
 ////
 
-#include <algorithm>
 #include <cassert>
 
 #include "history.h"
@@ -123,7 +122,7 @@ void MovePicker::go_next_phase() {
   case PH_GOOD_CAPTURES:
       lastMove = generate_captures(pos, moves);
       score_captures();
-      std::sort(moves, lastMove);
+      sort_moves(moves, lastMove);
       return;
 
   case PH_KILLERS:
@@ -134,7 +133,7 @@ void MovePicker::go_next_phase() {
   case PH_NONCAPTURES:
       lastMove = generate_noncaptures(pos, moves);
       score_noncaptures();
-      std::sort(moves, lastMove);
+      sort_moves(moves, lastMove);
       return;
 
   case PH_BAD_CAPTURES:
@@ -142,20 +141,20 @@ void MovePicker::go_next_phase() {
       // to get SEE move ordering.
       curMove = badCaptures;
       lastMove = lastBadCapture;
-      std::sort(badCaptures, lastMove);
+      sort_moves(badCaptures, lastMove);
       return;
 
   case PH_EVASIONS:
       assert(pos.is_check());
       lastMove = generate_evasions(pos, moves, pinned);
       score_evasions();
-      std::sort(moves, lastMove);
+      sort_moves(moves, lastMove);
       return;
 
   case PH_QCAPTURES:
       lastMove = generate_captures(pos, moves);
       score_captures();
-      std::sort(moves, lastMove);
+      sort_moves(moves, lastMove);
       return;
 
   case PH_QCHECKS:
-- 
2.39.2