QUICKSORT: how to resolve java.lang.StackOverflowError?

Question

I am writing a quicksort program to run with an input size of 100,000. I tried to run it with a size of 500 and it works fine, but with millions of inputs the program aborts with the following error code

"java.lang.StackOverflowError"

Can someone please help me solve this problem? I am pretty sure that endless recursion won't catch me. There is a base register that a recursive method should return.

public class count_comparisons { public static int count_comp =0; public static int partitioning(int[] A, int lo, int hi) { int pivot = A[lo]; int i=lo+1; int j=lo+1; int k=lo; for ( j=lo+1;j<=hi;j++) { if (A[j] < pivot) { swap(A,i,j); i++; } } swap(A,i-1,lo); return i-1; } public static int quicksort(int[] A, int lo, int hi) { if (lo>=hi) return 0; int pivot = partitioning(A,lo,hi); //StdOut.println("Pivot index is "+ pivot +" and entry at pivot is " + A[pivot]); StdOut.println("Lo is "+ lo +" and Hi is " + hi); int h = quicksort(A,lo,pivot-1); int m = quicksort(A,pivot+1,hi); //StdOut.println("First half count is "+h); //StdOut.println("Second half count is "+m); count_comp = count_comp + h + m; return (hi-lo); } public static void quicksort(int[] A,int N) { int k = quicksort(A,0,N-1); count_comp = count_comp + k; //StdOut.println(" First count is "+k); } private static void swap(int[] A, int j,int k) { int temp = A[j]; A[j] = A[k]; A[k] = temp; } public static void main(String[] args) { In in = new In("input_file.txt"); int N=569; int[] A = new int[569]; int i=0; while (!in.isEmpty()) { A[i++] = in.readInt(); } count_comparisons.quicksort(A,N); for( int h=0;h<N;h++) {} //StdOut.print(A[h]); StdOut.println(); StdOut.println(count_comparisons.count_comp); } } 

Answer 1

The recursion does not have to be infinite to cause a stack overflow: all it needs is simple enough to overflow the stack.

Quicksort can be very slow: in some particularly unfortunate circumstances, it may take up to n-1 invocations, for the worst O(n^2) performance.

You have two options: rewrite the code without recursion, using the explicit stack data structure or increasing the size of the stack that the JVM allocates to your program threads.

Answer 2

There is a trick to eliminating tail recursion and recursing only into a smaller subset that limits the depth of the recursion.