torch/torch7-distro — pull request #176 by jucor (2013-10-16 18:17:46+00:00)
Title: Speed-up qsort for sorted arrays

Hi guys

The current torch.sort() is a quicksort whose worst-case is O(N^2) on already sorted arrays -- a setup that happens often in practice. This pull request done with @d11 speeds it up back to O(N log N), by using the common trick of changing the pivot to the middle element of the partition. This moves the worst-case to some very rare configurations.
We also add some unit tests to make sure sorting still works, and a little script to benchmark the running times.

Runtime comparison between sorting a random array and a sorted array, as a function of tensor size, before modification:
![timesortbefore](https://f.cloud.github.com/assets/660037/1345369/a680ddba-368e-11e3-8bfb-86baeebee188.png)

and after modification:
![timesort](https://f.cloud.github.com/assets/660037/1345397/25bde8ac-368f-11e3-88c4-7858d8e97e4f.png)