-// Note that operator< is set up such that std::sort() will sort in descending order
-inline bool operator<(const MoveStack& f, const MoveStack& s) { return s.score < f.score; }
+inline bool operator<(const MoveStack& f, const MoveStack& s) { return f.score < s.score; }
+
+// An helper insertion sort implementation, works with pointers and iterators
+template<typename T, typename K>
+inline void insertion_sort(K firstMove, K lastMove)
+{
+ T value;
+ K cur, p, d;
+
+ if (firstMove != lastMove)
+ for (cur = firstMove + 1; cur != lastMove; cur++)
+ {
+ p = d = cur;
+ value = *p--;
+ if (*p < value)
+ {
+ do *d = *p;
+ while (--d != firstMove && *--p < value);
+ *d = value;
+ }
+ }
+}
+
+// Our dedicated sort in range [firstMove, lastMove), first splits
+// positive scores from ramining then order seaprately the two sets.
+template<typename T>
+inline void sort_moves(T* firstMove, T* lastMove, T** lastPositive)
+{
+ T tmp;
+ T *p, *d;
+
+ d = lastMove;
+ p = firstMove - 1;
+
+ d->score = -1; // right guard
+
+ // Split positives vs non-positives
+ do {
+ while ((++p)->score > 0) {}
+
+ if (p != d)
+ {
+ while (--d != p && d->score <= 0) {}
+
+ tmp = *p;
+ *p = *d;
+ *d = tmp;
+ }