How many random numbers can I get with .nextInt() from Random class in Java?

Question

SOLVED: I was instantiating a new Random object with every recursive call. I put it as a static variable out of Quicksort and now it works perfectly fine.

I'm programming Quicksort in Java for a school homework, but i got stuck. I'm choosing pivots randomly using nextInt() method from Random class. This means that i'm calling nextInt() in every recursive step. My quicksort does the work perfectly in arrays with 20000 elements. But when I try to sort an array with 40000 elements, this StackOverflowError appears

   java.lang.StackOverflowError: null (in java.util.Random)

I've searched this error on google buy nothing helps me. My guess is that I ran out of random ints, but i'm so noob in java that i don't even buy my own guess.

Here's my code (spanish is my first language, sorry for the lame english and the spanish code)

public static void quicksort(String[] A, int min, int max){// llamar ord(A, 0, n-1);
    if(min >= max){
        return;
    }
    Random rand = new Random(); 
    int pivote = particionar(A, min, max, rand);
    quicksort(A, min, pivote-1);
    quicksort(A, pivote + 1, max);
    }

public static int particionar(String[] A, int min, int max, Random rand){    
    int menores = min + 1;
    int mayores = max;

    int pivote = rand.nextInt(max-min+1) + min;
    String pivotstr = A[pivote];
    //dejar pivote al principio
    String aux = A[min];
    A[min] = A[pivote];
    A[pivote] = aux;

    while(menores <= mayores){
        if(A[menores].compareTo(pivotstr) <= 0){
            menores++;
        }
        else{//intercambiar
            String aux2 = A[menores];
            A[menores] = A[mayores];
            A[mayores] = aux2;
            mayores--;
        }
    }
    //mover pivote donde corresponde
    String aux3 = A[min];
    A[min] = A[mayores];
    A[mayores] = aux3;

    return mayores;

}

Answer 1

Your program is generating too many levels of recursive calls and running out of memory on the stack. One solution is to increase the stack size at run time as described here. The other is to convert from recursion to iteration, as suggested by lorenzo.marcon.

Java's default random number generator is a linear congruential generator with a 48 bit seed size, so it should have a cycle length on the order of 2**48. That means you don't run out of random ints, but rather you repeat the sequence after that many values.

A huge contributor to your stack overflow problem is that you're instantiating a new Random object with every recursive call. You wouldn't dig a new well every time you want a drink of water, most people would dig a single well and revisit it for more water. Similarly, recommended practice is to instantiate one static Random object and revisit it for more values unless you really know what you're doing - You almost never want multiple Random objects.