multithreaded quicksort in java

Question

I have been trying to write a multithreaded quicksort program using java. There are a lot of samples online using ThreadPool, CountDownLatch, etc..

However, i want just to use a count to keep count of the number of threads created.

The logic behind the program is:

1.  The main thread calls the parallel quicksort method
2.  The method partitions the array and check for the number of current threads
3.  Spawn new threads for next step using the same parallel method
4.  Or use the single normal quicksort method

I have been gaining performance using the parallel way but it isn’t that much. can someone help me to improve the codes?

here is what I’ve done:

class Quicksort extends Thread {
        private int arr[];
        private int low,high;
        public static int numThreads = Runtime.getRuntime().availableProcessors();
        public static int count = 0;

        public Quicksort(int[] arr, int low, int high){
            this.arr = arr;
            this.low = low;
            this.high = high;
        }

        public void run(){
            parallelQuicksort(arr,low,high);    
        }

        public static void quicksort(int[] arr, int low, int high){
            if (high>low){
                int i = partition(arr,low,high);
                quicksort(arr,low,i-1);
                quicksort(arr,i+1,high);
            }
        }

        public static  void parallelQuicksort(int[] arr, int low, int high){
            if (high>low){
                int i = partition(arr,low,high);
                if (count < numThreads){
                    count++;
                    Quicksort quicksort  = new Quicksort(arr, low, i-1);
                    quicksort.start();
                    try{
                        quicksort.join();
                    }
                    catch (InterruptedException e){}
                }
                else{
                    quicksort(arr,low,i-1);
                }   
                if (count < numThreads){
                    count++;
                    Quicksort quicksort  = new Quicksort(arr, i+1, high);
                    quicksort.start();
                    try{
                        quicksort.join();
                    }
                    catch (InterruptedException e){}
                }
                else{
                    quicksort(arr,i+1,high);
                }   
            }
        }

        public static int partition(int[] A, int l,int r)

        public static void swap(int[] A,int i,int j)

        public static int median(int[] A,int l,int mid,int r)
}

The main class:

public class Test{
    public static void main(String[] args) {
    //generate random array of size 1000000

    long start = System.currentTimeMillis();

    Quicksort.quicksort(arr,0,arr.length -1);

    System.out.println("Single array sorted in "+(System.currentTimeMillis()-start)+" ms");

    start = System.currentTimeMillis();

    Quicksort.parallelQuicksort(arr2,0,arr.length -1);

    System.out.println("Threaded array sorted in "+(System.currentTimeMillis()-start)+" ms");
    }
}

The sample output i am getting:

Single array sorted in 393 ms
Threaded array sorted in 367 ms

Single array sorted in 325 ms
Threaded array sorted in 305 ms

Single array sorted in 344 ms
Threaded array sorted in 320 ms

Answer 1

Your biggest problem here is that you are joining right after you start a new thread. This causes the calling thread to wait for the new thread to finish. You need to start up all of your threads that you intent to run concurrently, and then wait for them once they're all running. So instead of:

Quicksort quicksort  = new Quicksort(arr, low, i-1);
quicksort.start();  // Start new thread.
quickstart.join();  // Wait for it to run before moving on

Quicksort quicksort = new Quicksort(arr, i+1, high);
quickstart.start(); // Start second thread (after first has finished)
quickstart.join(); // Wait for second thread.

You need to do something more like this:

Quicksort low = new Quicksort(arr, low, i-1);
low.start(); // Start first thread
Quicksort high = new Quicksort(arr, i+1, high);
high.start(); // While first thread is running, start second.
low.join(); // Wait for first thread.
high.join(); // Immediately returns if already finished

The above code, which is what I think you intended to write, is still inefficient. It doesn't assign any work to the main thread while it's waiting for the other threads to finish.

Along with these issues, the way you've written it, once a thread is finished, the count doesn't decrease. Instead, the main thread just picks up more work. Which means that you aren't distributing load correctly.

As @Sergei said in the comments, you might want to look into the Fork/Join framework to manage threads. Fork/Join in Java allows you to split up work into tasks, and to queue them up so they are assigned to spare threads. If you want to limit the number of threads you are using, you can do so by setting the desired level of parallelism when you create the ForkJoinPool.

ForkJoinPool pool = new ForkJoinPool(numThreads);

Although, the defaut is set to the number of available processors, and unless you have a reason to change it, then don't.

A tutorial on how to write quicksort using the Java Fork/Join libraries is available here.

And on a separate point, you are overusing static methods. They should be instance methods. Have a look here for details on when to use static methods.