title: Fastest sort algorithm for millions of UINT64 RGBZ graphics pixels
body: <p>I am sorting 10+ million <code>uint64_t</code>s with RGB data from .RAW files and 79% of my C program time is spent in <code>qsort</code>. I am looking for a faster sort for this specific data type.</p>
  <p>Being RAW graphical data, the numbers are very random and ~80% unique. No partial sorting or runs of sorted data can be expected. The 4 <code>uint16_t</code>s inside the <code>uint64_t</code> are R, G, B and zero (possibly a small count &lt;= ~20).</p>
  <p>I have the simplest comparison function I can think of using <code>unsigned long long</code>s (you CANNOT just subtract them):</p>
  <pre><code>qsort(hpidx, num_pix, sizeof(uint64_t), comp_uint64); 
  ...
  int comp_uint64(const void *a, const void *b)  {
      if(*((uint64_t *)a) &gt; *((uint64_t *)b))  return(+1);
      if(*((uint64_t *)a) &lt; *((uint64_t *)b))  return(-1);
      return(0);
  }  // End Comp_uint64().
  </code></pre>
  <p>There was a very interesting &quot;Programming Puzzles &amp; Code Golf&quot; on StackExchange, but they used <code>float</code>s. Then there are QSort, RecQuick, heap, stooge, tree, radix...</p>
  <p>The swenson/sort looked interesting but had no (obvious) support for my datatype, <code>uint64_t</code>. And the &quot;quick sort&quot; time was the best. Some sources say the system <code>qsort</code> can be anything, not necessarily &quot;Quick Sort&quot;.</p>
  <p>A C++ sort bypasses the generic casting of void pointers and realizes great improvements in performance over C. There has to be an optimized method to slam U8s through a 64bit processor at warp speed.</p>
  <hr />
  <p>System/compiler info:</p>
  <p>I am currently using the GCC with Strawberry Perl</p>
  <pre><code>gcc version 4.9.2 (x86_64-posix-sjlj, built by strawberryperl.com
  Intel 2700K Sandy Bridge CPU, 32GB DDR3
  windows 7/64 pro
  
  gcc -D__USE_MINGW_ANSI_STDIO -O4 -ffast-math -m64 -Ofast -march=corei7-avx -mtune=corei7 -Ic:/bin/xxHash-master -Lc:/bin/xxHash-master c:/bin/stddev.c -o c:/bin/stddev.g6.exe 
  </code></pre>
  <hr />
  <h1>First attempt at a better <code>qsort</code>, <code>QSORT()</code>!</h1>
  <p>Tried to use Michael Tokarev's inline <code>qsort</code>.</p>
  <p>&quot;READY-TO-USE&quot;?  From <code>qsort.h</code> documentation</p>
  <pre><code>-----------------------------
  * Several ready-to-use examples:
   *
   * Sorting array of integers:
   * void int_qsort(int *arr, unsigned n) {
   * #define int_lt(a,b) ((*a)&lt;(*b))
   *   QSORT(int, arr, n, int_lt);
  --------------------------------
  
  Change from type &quot;int&quot; to &quot;uint64_t&quot;
  compile error on TYPE???
      
      c:/bin/bpbfct.c:586:8: error: expected expression before 'uint64_t'
        QSORT(uint64_t, hpidx, num_pix, islt);
  </code></pre>
  <p>I can't find a real, compiling, working example program, just comments with the &quot;general concept&quot;</p>
  <pre><code>#define QSORT_TYPE uint64_t 
  #define islt(a,b) ((*a)&lt;(*b))
  
  uint64_t *QSORT_BASE; 
  int QSORT_NELT;
  
  hpidx=(uint64_t *) calloc(num_pix+2, sizeof(uint64_t));  // Hash . PIDX
  QSORT_BASE = hpidx;
  QSORT_NELT = num_pix;  // QSORT_LT is function QSORT_LT()
  QSORT(uint64_t, hpidx, num_pix, islt);  
  //QSORT(uint64_t *, hpidx, num_pix, QSORT_LT);  // QSORT_LT mal-defined?
  //qsort(hpidx, num_pix, sizeof(uint64_t), comp_uint64); // &lt;&lt; WORKS
  </code></pre>
  <p>The &quot;ready-to-use&quot; examples use types of <code>int</code>, <code>char *</code> and <code>struct elt</code>. Isn't <code>uint64_t</code> a type?? Try <code>long long</code></p>
  <pre><code>QSORT(long long, hpidx, num_pix, islt); 
  c:/bin/bpbfct.c:586:8: error: expected expression before 'long'
   QSORT(long long, hpidx, num_pix, islt);
  </code></pre>
  <hr />
  <h1>Next attempt: <code>RADIXSORT</code>:</h1>
  <p>Results:  RADIX_SORT is RADICAL!</p>
  <pre><code>  I:\br3\pf.249465&gt;grep &quot;Event&quot; bb12.log | grep -i Sort       
   &lt;&lt; 1.40 sec average
  4) Time=1.411 sec    = 49.61%, Event RADIX_SORT        , hits=1
  4) Time=1.396 sec    = 49.13%, Event RADIX_SORT        , hits=1
  4) Time=1.392 sec    = 49.15%, Event RADIX_SORT        , hits=1
  16) Time=1.414 sec    = 49.12%, Event RADIX_SORT        , hits=1
  
  I:\br3\pf.249465&gt;grep &quot;Event&quot; bb11.log | grep -i Sort 
   &lt;&lt; 5.525 sec average  = 3.95 time slower
  4) Time=5.538 sec    = 86.34%, Event QSort             , hits=1
  4) Time=5.519 sec    = 79.41%, Event QSort             , hits=1
  4) Time=5.519 sec    = 79.02%, Event QSort             , hits=1
  4) Time=5.563 sec    = 79.49%, Event QSort             , hits=1
  4) Time=5.684 sec    = 79.83%, Event QSort             , hits=1
  4) Time=5.509 sec    = 79.30%, Event QSort             , hits=1
  </code></pre>
  <p>3.94 times faster than whatever sort <code>qsort</code> out of the box uses!</p>
  <p>And, even more importantly, there was actual, working code, not just 80% of what you need given by some Guru who assumes you know everything they know and can fill in the other 20%.</p>
  <p>Fantastic solution! Thanks Louis Ricci!</p>