[Courgette] Fix sorting in QSufSort's split().

courgette/third_party/qsufsort.h

 /*
   qsufsort.h -- Suffix array generation.
 
   Copyright 2003 Colin Percival
 
   For the terms under which this work may be distributed, please see
   the adjoining file "LICENSE".
 
   ChangeLog:
   2005-05-05 - Use the modified header struct from bspatch.h; use 32-bit
                values throughout.
                  --Benjamin Smedberg <benjamin@smedbergs.us>
   2010-05-26 - Use a paged array for V and I. The address space may be too
                fragmented for these big arrays to be contiguous.
                  --Stephen Adams <sra@chromium.org>
-  2015-08-03 - Extrat qsufsort to a separate file as template.
+  2015-08-03 - Extract QSufSort to a separate file as template.
                  --Samuel Huang <huangs@chromium.org>
   2015-08-19 - Optimize split() and search(), add comments.
                  --Samuel Huang <huangs@chromium.org>
+  2016-04-27 - Change split() to use Bentley & McIlroy's pivot selection
+               algorithm, which QSufSort originally used. Reference:
+               http://www.larsson.dogma.net/qsufsort.c
+                 --Samuel Huang <huangs@chromium.org>
 */
 
 #include <algorithm>
 #include <cstring>
 
 namespace courgette {
 namespace qsuf {
 
 // ------------------------------------------------------------------------
 //
 // The following code is taken verbatim from 'bsdiff.c'. Please keep all the
 // code formatting and variable names.  The changes from the original are:
 // (1) replacing tabs with spaces,
 // (2) indentation,
 // (3) using 'const',
 // (4) changing the V and I parameters from int* to template <typename T>.
 // (5) optimizing split() and search(); fix styles.
 //
 // The code appears to be a rewritten version of the suffix array algorithm
 // presented in "Faster Suffix Sorting" by N. Jesper Larsson and Kunihiko
 // Sadakane, special cased for bytes.
 
-template <typename T> static void split(T I, T V, int start, int end, int h) {
+namespace {
+
+template <typename T> T median3(const T& a, const T& b, const T& c) {
+  if (a < b)
+    return b < c ? b : (a < c ? c : a);
+  return b > c ? b : (a > c ? c : a);
+}
+
+}  // namespace
+
+template <typename T> void split(T I, T V, int start, int end, int h) {
   // For small interval, apply selection sort.
-  if (end - start < 6) {
+  if (end - start < 16) {
     for (int i = start; i < end; ) {
       int skip = 1;
       int best = V[I[i] + h];
       for (int j = i + 1; j < end; j++) {
         int cur = V[I[j] + h];
         if (best > cur) {
           best = cur;
           int tmp = I[i];
           I[i] = I[j];
           I[j] = tmp;
@@ skipping 10 matching lines @@
         I[i] = -1;
       } else {
         for (int j = i, jend = i + skip; j < jend; j++)
           V[I[j]] = jend - 1;
       }
       i += skip;
     }
     return;
   }
 
+  // Select pivot, algorithm by Bentley & McIlroy.
+  int n = end - start;
+  int mid = start + (n >> 1);
+  int pivot = V[I[mid] + h];
+  int p1 = V[I[start] + h];
+  int p2 = V[I[end - 1] + h];
+  if (n > 40) {  // Big array: Pseudomedian of 9.
+    int s = n >> 3;
+    pivot = median3(pivot, V[I[mid - s] + h], V[I[mid + s] + h]);
+    p1 = median3(p1, V[I[start + s] + h], V[I[start + s + s] + h]);
+    p2 = median3(p2, V[I[end - 1 - s] + h], V[I[end - 1 - s - s] + h]);
+  }  // Else medium array: Pseudomedian of 3.
+  pivot = median3(pivot, p1, p2);
+
   // Split [start, end) into 3 intervals:
   //   [start, j) with secondary keys < pivot,
   //   [j, k) with secondary keys == pivot,
   //   [k, end) with secondary keys > pivot.
-  int pivot = V[I[(start + end) / 2] + h];
   int j = start;
   int k = end;
   for (int i = start; i < k; ) {
     int cur = V[I[i] + h];
     if (cur < pivot) {
       if (i != j) {
         int tmp = I[i];
         I[i] = I[j];
         I[j] = tmp;
       }
@@ skipping 100 matching lines @@
   }
   *pos = I[hi];
   return y;
 }
 
 //  End of 'verbatim' code.
 // ------------------------------------------------------------------------
 
 }  // namespace qsuf
 }  // namespace courgette