torch/torch7-distro — pull request #198 by jucor (2013-11-13 17:04:16+00:00)
Title: Better qsort implementation from reference article

Hi guys

As discussed with Koray, this pull request replaces the wikipedia-based-then-improved handmade implementation by an implementation from a reference academic article by Sedgewick (who did his thesis with Knuth on quicksort):

Sedgewick's 1978 "Implementing Quicksort Programs"
http://www.csie.ntu.edu.tw/~b93076/p847-sedgewick.pdf

It is the state of the art existing implementation of regular single-pivot quicksort. The macros are here to make as close a match as possible to the pseudocode of Program 2 p.851.

Here are the benchmarks against the existing implementation:

![benchmarkratio](https://f.cloud.github.com/assets/660037/1533420/477e02b8-4c85-11e3-96a4-594b19263f16.png)
![benchmarktime](https://f.cloud.github.com/assets/660037/1533421/478df0a6-4c85-11e3-9477-d2afe206432d.png)

As you can see, although we loose a little on very small arrays (which are so fast to sort that it is not noticeable), we gain up to 50% on constant arrays, and 10% on random arrays. We can even see the difference when some caching stops being done for large array sizes.

The advantage, beyond this reasonable improvement, is also that we now have a proper reference, with details about each carefuly made implementation decision by Sedgewick.

Note that I have only done the ascending sort, leaving the descending sort as it was for comparison purposes. If you decide to merge this branch, I will copy/paste the code and change the inequalities to get the descending sort.
Cheers.