Merge-sort using Multi-threading

Question

I tried to parallelize merge-sort using multi-threading.Here is my code (please forgive if it poorly implemented.I did not care about the space-complexity of the program). I am achieving the sorted array.My question is:Will this process actually reduce the time taken to sort an array of large size?What all modifications are needed to make it efficient and is it o any use?

import java.io.IOException;
import java.util.Arrays;
import java.util.Random;
import java.util.Scanner;

public class Merge {
    public static int[] inputArray;
    public static int[] arr1;
    public static int[] arr2;
    public static int[] arr3;
    public static int t1_status=0;
    public static int t2_status=0;

    public static void main(String[] args) throws IOException{

        System.out.println("Enter the length of the array");

        Scanner in =new Scanner(System.in);

        int arraySize=in.nextInt();

        inputArray = new int[arraySize];

        Random rand=new Random();

        for(int i=0;i<arraySize;i++)
        {
            inputArray[i]=rand.nextInt(100);
        }

        //diving the original array into two subarrays

        arr1=Arrays.copyOfRange(inputArray, 0, inputArray.length/2);

        arr2=Arrays.copyOfRange(inputArray, (inputArray.length)/2,inputArray.length);
        //printing the original array
        System.out.print("The original array is array is ");

        for(int h:inputArray)
        {
            System.out.println(h);
        }

        Thread t1=new Thread(new Runnable(){
                public void run() 
                {
                    mergeSort(arr1);
                    System.out.println("t1 started");
                }

            });
        Thread t2=new Thread(new Runnable(){
                public void run()
                {
                    mergeSort(arr2);
                    System.out.println("t2 started");
                }

            });
        //starting threads
        t1.start();
        t2.start();

        try {
            t1.join();
            t2.join();
        }
        catch (InterruptedException e) {
            // TODO Auto-generated catch block
            e.printStackTrace();
        }
        if(t1.isAlive())
        {
            t1_status=1;
        }
        if(t2.isAlive())
        {
            t2_status=1;
        }
        t1.stop();
        t2.stop();

        arr3=new int[inputArray.length];

        merge(arr3,arr1,arr2);//merging arr1 and arr2.At this point both arr1 and arr2 are sorted.

        System.out.println("The sorted array is ");
        for(int m:arr3)
        {
            System.out.print(m);
            System.out.print(" ");
        }
        System.out.println(" ");
    }

    static void mergeSort(int[] A)
    {
        if (A.length > 1) 
        {
            int q = A.length/2;

            int[] leftArray = Arrays.copyOfRange(A, 0, q);
            int[] rightArray = Arrays.copyOfRange(A,q,A.length);
            mergeSort(leftArray);
            mergeSort(rightArray);
            merge(A,leftArray,rightArray);
        }
    }
    //merge function

    static void merge(int[] a, int[] l, int[] r) {
        int totElem = l.length + r.length;

        int i,li,ri;
        i = li = ri = 0;
        while ( i < totElem) {
            if ((li < l.length) && (ri<r.length)) {
                if (l[li] < r[ri]) {
                    a[i] = l[li];
                    i++;
                    li++;
                }
                else {
                    a[i] = r[ri];
                    i++;
                    ri++;
                }
            }
            else {
                if (li >= l.length) {
                    while (ri < r.length) {
                        a[i] = r[ri];
                        i++;
                        ri++;
                    }
                }
                if (ri >= r.length) {
                    while (li < l.length) {
                        a[i] = l[li];
                        li++;
                        i++;
                    }
                }
            }
        }

        if(t1_status==1){arr1=a;}
        else if(t2_status==1){arr2=a;}
        else{arr3=a;}
    }
}

Answer 1

See the Collections.parallelSort() and the Fork/Join framework javadoc.

The small enough arrays are sorted as legacy on single thread, but when large enough (8192, I think), the parallelSort will divide and conquer, with the ForkJoinPool default pool (as many threads as there are cores).

Using only 2 threads is probably doubling your speed, but not more.

FYI, the launcher thread should work too, not just sit there joining. It can take the job of the 2nd thread for instance. Then only join once.

Answer 2

Sorting both halves in separate threads is a good start, but you can make use of parallelism through the merging, too.

Also, you should recurse do the subsorts in parallel, too... BUT keep track of the depth of recursion, and stop making new threads when you're already using all your cores. Making new threads for those tiny little leaf sorts is a huge overhead.

All together:

1. Split into 2 threads
2. First, Thread 1 sorts the front half of the source array and Thread 2 sorts the back half of the source array. To sort the haves, they either call this function recursively or switch to a serial sort if 2^recursion_depth > number_of_cores; then
3. Thread 1 does a forward merge of both halves into the front half of the destination, and Thread 2 does a backward merge of both halves into the back half of destination. They both stop when they reach the midpoint of the destination.

Answer 3

Yes it can help, quite a bit depending on how many cores do you have and how big your array is. Spawning threads and coordinating work isn't free. There's a soft spot on how many parallel threads are actually useful.

I think you're doing too little,but this is very easy to overdo: Since the process is CPU-bound you want one thread for each core.

A fixed thread pool/executor is handy here.

Check out some example performance gains at CSE373:Data Structures and Algorithms/MergeSort.