Quello che dice andbin in teoria è vero, solo che nel nostro caso abbiamo a che fare con la JVM che si occupa di associare le risorse alla CPU o alle CPU quindi se abbiamo a che fare con una JVM che non è ottimizzata per il multi core farà eseguire sempre e comunque tutto ad uno stesso core e a quel punto Hyper-Threading e roba varia va a farsi benedire.

Cmq per ottimizzare il tuo programma io utilizzerei le code. Nel senso che metterei il mio array in una coda e poi farei partire un numero arbitrario di thread es. da min 2 max 10 che attingono tutti dalla stessa coda. Quando la coda è vuota termino i threads.