Java: Paralelización de ordenación rápida a través de subprocesos múltiples

Estoy experimentando con algoritmos de paralelización en Java. Comencé con un tipo de fusión y publiqué mi intento en estepregunta. Mi intento revisado está en el código a continuación, donde ahora trato de paralelizar la ordenación rápida.

¿Hay algún error de novato en mi implementación o enfoque de subprocesos múltiples para este problema? Si no es así, ¿no debería esperar un aumento de velocidad de más del 32% entre un algoritmo secuencial y uno paralelo en un núcleo de duelo (ver los tiempos al final)?

Aquí está el algoritmo multihilo:

    public class ThreadedQuick extends Thread
    {
        final int MAX_THREADS = Runtime.getRuntime().availableProcessors();

        CountDownLatch doneSignal;
        static int num_threads = 1;

        int[] my_array;
        int start, end;

        public ThreadedQuick(CountDownLatch doneSignal, int[] array, int start, int end) {
            this.my_array = array;
            this.start = start;
            this.end = end;
            this.doneSignal = doneSignal;
        }

        public static void reset() {
            num_threads = 1;
        }

        public void run() {
            quicksort(my_array, start, end);
            doneSignal.countDown();
            num_threads--;
        }

        public void quicksort(int[] array, int start, int end) {
            int len = end-start+1;

            if (len <= 1)
                return;

            int pivot_index = medianOfThree(array, start, end);
            int pivotValue = array[pivot_index];

            swap(array, pivot_index, end);

            int storeIndex = start;
            for (int i = start; i < end; i++) {
               if (array[i] <= pivotValue) {
                   swap(array, i, storeIndex);
                   storeIndex++;
               }
            }

            swap(array, storeIndex, end);

            if (num_threads < MAX_THREADS) {
                num_threads++;

                CountDownLatch completionSignal = new CountDownLatch(1);

                new ThreadedQuick(completionSignal, array, start, storeIndex - 1).start();
                quicksort(array, storeIndex + 1, end);

                try {
                    completionSignal.await(1000, TimeUnit.SECONDS);
                } catch(Exception ex) {
                    ex.printStackTrace();
                }
            } else {
                quicksort(array, start, storeIndex - 1);
                quicksort(array, storeIndex + 1, end);
            }
        }
    }

Así es como empiezo:

ThreadedQuick.reset();
CountDownLatch completionSignal = new CountDownLatch(1);
new ThreadedQuick(completionSignal, array, 0, array.length-1).start();
try {
    completionSignal.await(1000, TimeUnit.SECONDS);
} catch(Exception ex){
    ex.printStackTrace();
}

Probé esto contra Arrays.sort y un algoritmo de ordenación rápida secuencial similar. Estos son los resultados de tiempo en una computadora portátil Intel Duel-Core Dell, en segundos:

Elementos: 500,000, secuencial: 0.068592, roscado: 0.046871, matrices.sort: 0.079677

Elementos: 1,000,000, secuencial: 0.14416, roscado: 0.095492, Arreglos.Orden: 0.167155

Elementos: 2,000,000, secuencial: 0.301666, roscado: 0.205719, Arreglos.Orden: 0.350982

Elementos: 4,000,000, secuencial: 0.623291, roscado: 0.424119, Arreglos.Orden: 0.712698

Elementos: 8,000,000, secuencial: 1.279374, roscado: 0.859363, Arreglos.Orden: 1.487671

Cada número anterior es el tiempo promedio de 100 pruebas, arrojando los 3 casos más bajos y los 3 más altos. Usé Random.nextInt (Integer.MAX_VALUE) para generar una matriz para cada prueba, que se inicializó una vez cada 10 pruebas con la misma semilla. Cada prueba consistió en cronometrar el algoritmo dado con System.nanoTime. Redondeé a seis decimales después de promediar. Y obviamente, verifiqué si cada tipotrabajó.

Como puede ver, hay un aumento de aproximadamente el 32% en la velocidad entre los casos secuenciales y roscados en cada conjunto de pruebas. Como pregunté anteriormente, ¿no debería esperar más que eso?