torch/torch7-distro — pull request #185 by jucor (2013-10-24 17:13:31+00:00)
Title: Fix quicksort on constant arrays

TL;DR: This pull-request fixes the slow time in sorting arrays with all elements being equal.

Long version:
As pointed by Tom in https://github.com/torch/torch7-distro/pull/176#issuecomment-26993416 , `torch.sort()` is extremely slow on arrays with long stretches of constant numbers.

This was due to the original quicksort implementation using a 'or-equal' inequality when comparing elements with the pivot during the partitioning. That was not a good idea: while both Wikipedia and Cormen et al's "Introduction to Algorithms" use a lower-or-equal comparison when partitioning, Sedgewick's Algorithms in C (first edition, 1990) discusses p. 120 quicksort for arrays with duplicated keys. It recommends to stop whenever you encounter an element equal to the pivot, so as to "balance-out" the partitions. See also his landmark article (which Cormen refers to): http://www.csie.ntu.edu.tw/~b93076/p847-sedgewick.pdf
Sedgewick did his whole PhD on Quicksort :)
And here's his whole paper on the topic of quicksort with equal keys.:
http://www.cs.auckland.ac.nz/~mcw/Teaching/refs/sorting/quicksort-equal-keys.pdf
In our case, this is salvation ;-)

I also added a tests on sorting with duplicate keys, which weren't checked until now.

Here are the timings before:
![timesortascending](https://f.cloud.github.com/assets/660037/1401051/8a788aa4-3ccf-11e3-8f67-040218229a2e.png)
and now:
![timesortascending](https://f.cloud.github.com/assets/660037/1401055/9285d77e-3ccf-11e3-829b-b67137569b94.png)