can sort an array of 10,000,000 Integers in a few seconds (on my modest 32-bit Linux workstation: Old and creaky, like me, but not as cranky as me). I just use the "out-of-the-box" default openjdk version 1.6 Java setup on my Centos 5.8 workstation; no special stack or heap enlargement.
According to Java documentation, the Arrays.sort
algorithm is "adapted from Jon L. Bentley and M. Douglas McIlroy's 'Engineering a Sort Function', Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November 1993)."
(From the Good Old Days at Bell Labs in Murray Hill.)
This work is also referenced, but not elaborated on by the Wikipedia page on Quicksort
Here's a copy of the paper that you should be able to download: http://cs.fit.edu/~pkc/classes/writi...ngineering.pdf
The methodology described in the paper is not pure quicksort,and it's not about Java, but maybe you can gain some insight by reading about how they surmounted some shortcomings of previous qsort library implementations...