Quicker Quicksort

A lot of we do requires sorting. For years, the best-of-breed was quicksort, perhaps with a randomizer pre-processor to avoid the worst-case scenario of already sorted data. BTW, here is a linear-time randomiser:

function nshuffle(a,  i,j,n,tmp) {
n=a[0]; # a has items at 1...n
for(i=1;i<=n;i++) {         
    j=i+round(rand()*(n-i));         
    tmp=a[j];         
    a[j]=a[i];         
    a[i]=tmp;   
 };  
return n;
}
function round(x) { return int(x + 0.5) } 

Now there is empirical evidence that a new quicksort that uses two (not one) pivots is faster:

• Pick an elements P1, P2, called pivots from the array.
  
• Assume that P1 <= P2, otherwise swap it.
• Reorder the array into three parts: those less than the smaller
  pivot, those larger than the larger pivot, and in between are
  those elements between (or equal to) the two pivots.
  
• Recursively sort the sub-arrays.
  

This new method is up to twice as fast as old quicksort.