title: Fast reverse sort in (SWI) Prolog
body: <p>I'm looking for a fast way to sort a list in reverse order in Prolog. Algorithmically it should perform as quickly as standard sort, but the options that I've come up with are much slower, for obvious reasons.</p>
  
  <p>Predicate <code>rsort1/2</code> sorts and then reverses.</p>
  
  <pre><code>rsort1(L1, L2) :-
      sort(L1, Tmp),
      reverse(Tmp, L2).
  </code></pre>
  
  <p>Predicate <code>rsort2/2</code> uses <code>predsort/3</code> with a custom comparator.</p>
  
  <pre><code>rsort2(L1, L2) :-
      predsort(reverse_compare, L1, L2).
  
  reverse_compare(Delta, E1, E2) :-
      compare(Delta, E2, E1).
  </code></pre>
  
  <p>To test their performance I've generated a huge random list like this:</p>
  
  <pre><code>?- Size = 1234567,
     findall(N, (between(1, Size, _), N is random(Size)), Ns),
     assert(test_list(Ns)).
  Size = 1234567,
  Ns = [183677, 351963, 737135, 246842, 22754, 1176800, 1036258|...].
  </code></pre>
  
  <p>These are the runtimes for the standard <code>sort</code>:</p>
  
  <pre><code>?- test_list(Ns), time(sort(Ns, NsS)).
  % 2 inferences, 7.550 CPU in 8.534 seconds (88% CPU, 0 Lips)
  Ns = [183677, 351963, 737135, 246842, 22754, 1176800, 1036258, 625628|...],
  NsS = [0, 1, 3, 5, 8, 10, 12, 14, 16|...].
  </code></pre>
  
  <p>... for <code>rsort1</code>:</p>
  
  <pre><code>?- test_list(Ns), time(rsort1(Ns, NsS)).
  % 779,895 inferences, 8.310 CPU in 9.011 seconds (92% CPU, 93850 Lips)
  Ns = [183677, 351963, 737135, 246842, 22754, 1176800, 1036258, 625628|...],
  NsS = [1234564, 1234563, 1234562, 1234558, 1234557, 1234556, 1234555|...].
  </code></pre>
  
  <p>... and for <code>rsort2</code>:</p>
  
  <pre><code>?- test_list(Ns), time(rsort2(Ns, NsS)).
  % 92,768,484 inferences, 67.990 CPU in 97.666 seconds (70% CPU, 1364443 Lips)
  Ns = [183677, 351963, 737135, 246842, 22754, 1176800, 1036258, 625628|...],
  NsS = [1234564, 1234563, 1234562, 1234558, 1234557, 1234556, 1234555|...].
  </code></pre>
  
  <p>Can I do better than <code>rsort1</code> and <code>rsort2</code> speedwise?</p>