Multithreading QuickSort in Java

Question

Can you help me with multithreading QuickSort in Java?

I have next problem : The time of work of quicksort with one thread more less than quicksort with 2 or 3 threads. What I did wrong?

I wrote next code for worker :

public class QuickSortWorker extends Thread {

    private int workerId;
    private double[] array;
    private int low;
    private int high;

    public QuickSortWorker(double[] array, int low, int high) {
        this.array = array;
        this.low = low;
        this.high = high;
        this.workerId = WorkerManager.workersCount++;
    }

    public void run() {
        System.out.println("Run new worker. ID: " + this.workerId);
        System.out.println("Worker status: " + this.isAlive());

        this.quickSort(this.array, this.low, this.high);

        System.out.println("Stop worker. ID: " + this.workerId);
        WorkerManager.workersCount--;
    }

    protected void quickSort(double[] array, int low, int high) {
        /*int i = low, j = high;
        double pivot = array[low + (high - low) / 2];

        while (i <= j) {
            while (array[i] < pivot) {
                i++;
            }

            while (array[j] > pivot) {
                j--;
            }

            if (i <= j) {
                this.exchange(array, i, j);
                i++;
                j--;
            }
        }

        if (low < j) {
            quickSort(array, low, j);
        }

        if (i < high) {
            sort(array, i, high);
        }*/

        int len = high - low + 1;
        if (len <= 1) {
            return;
        }

        double pivot = array[low + (high - low) / 2];
        exchange(array, low + (high - low) / 2, high);

        int storeIndex = low;
        for (int i = low; i < high; i++) {
            if (array[i] < pivot) {
                exchange(array, i, storeIndex);
                storeIndex++;
            }
        }

        exchange(array, storeIndex, high);

        sort(array, low, storeIndex - 1);
        quickSort(array, storeIndex + 1, high);
    }

    protected void exchange(double[] array, int i, int j) {
        double tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }

    protected void sort(double[] array, int low, int high) {
        if (WorkerManager.workersCount < WorkerManager.WORKERS_LIMIT) {
            try {
                WorkerManager.createWorker(array, low, high);
            } catch (InterruptedException e) {
                System.out.println("QuickSort worker was down. Reason: " + e.getMessage() + "\n");
                e.printStackTrace();
            }
        } else {
            this.quickSort(array, low, high);
        }
    }
}

And next code for WorkerManager :

public class WorkerManager {

    public static final int MAX_WORKER_COUNT = 10;
    public static int WORKERS_LIMIT = 0;
    public static int workersCount = 0;

    private double _startTime = 0;
    private double _stopTime = 0;
    private double _workTime = 0;

    public void createTask(double[] data, int workerCount) throws WorkerManagerException {  
        if (workerCount > MAX_WORKER_COUNT) {
            throw new WorkerManagerException("Worker count cant be more than " + MAX_WORKER_COUNT);
        }

        try {
            WORKERS_LIMIT = workerCount;
            this.startTimer();
            WorkerManager.createWorker(data, 0, data.length - 1);
            this.stopTimer();

            System.out.println("\nWorktime: " + this.getWorkTime() + " milliseconds.");
        } catch (InterruptedException e) {
            System.out.println("QuickSort worker was down. Reason: " + e.getMessage() + "\n");
            e.printStackTrace();
        }
    }

    public static void createWorker(double[] array, int low, int high) throws InterruptedException {
        QuickSortWorker worker = new QuickSortWorker(array, low, high);
        worker.start();
        worker.join();
    }

    protected void startTimer() {
        this._startTime = System.currentTimeMillis(); 
    }

    protected void stopTimer() {
        this._stopTime = System.currentTimeMillis();
    }

    private void setWorkTime() {
        this._workTime = (this._startTime == 0)
                ? 0
                : this._stopTime - this._startTime;
    }

    private double getWorkTime() {
        if (this._workTime == 0) {
            this.setWorkTime();
        }
        return this._workTime;
    }
}

Answer 1

You create workers in main thread, and once started you block main thread (join) and wait for the worker to finish:

 QuickSortWorker worker = new QuickSortWorker(array, low, high);
 worker.start();
 worker.join();

This will not give you the desired parallelism. At any given time there is only one thread working - that's why there is no performance gain.