Thread: Stackoverflow Recursive quicksort

For my quicksort for fun I wrote, when I time it, it has no problem sorting 1000 items in order or random data of size 1000, 10K, 100K, 1M, but when it comes to applying it to 10K descending order of data, I get a stack overflow? I'm using Windows 7 64-bit core i5 Sandy bridge. I tried to set memory via > java -Xmx2g for example but it's limited and also this is for heap size to increase, not stack size which is what the quick sort I wrote is using, so should I use JVM 64-bit?

EDIT: I just found out you can increase stack size, I'll try this first

How many times does the method call itself? Stackoveflow is usually because of runaway recursion.

java.util.Arrays.sort() 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...


Cheers!

Z