Merge sort algorithm is slower on multi thread

Question

For my class I have to implement merge sort algorithm in multi thread and compare its time to single thread version. I know that it should be faster but times that I get says otherwise. Multi threaded version becomes faster for arrays with size 1000000+ and even then it isn't significant difference. I am providing code that I am using. Am I doing something wrong? I don't have much experience in multi-threading

public Sorter() {  


public void mergeSortMultiThread(int[] array, int start, int end){
    if(start < end){
        // Find the middle point
        int m = (start+end)/2;
        Thread t1 = new Thread(() -> mergeSortSequence(array, start, m));
        t1.start();
        mergeSortSequence(array , m+1, end);
        try {
            t1.join();
        } catch (InterruptedException e) {
            e.printStackTrace();
        }

        // Merge the sorted halves
        merge(array, start, m, end);
    }
}

public void mergeSortSnngleThread(int[] array, int start, int end){
    if(start < end){
        // Find the middle point
        int m = (start+end)/2;

        // Sort first and second halves
        mergeSortSequence(array, start, m);
        mergeSortSequence(array , m+1, end);

        // Merge the sorted halves
        merge(array, start, m, end);
    }
}

private void merge(int arr[], int l, int m, int r)
{
    // Find sizes of two subarrays to be merged
    int n1 = m - l + 1;
    int n2 = r - m;

    /* Create temp arrays */
    int L[] = new int [n1];
    int R[] = new int [n2];

    /*Copy data to temp arrays*/
    for (int i=0; i<n1; ++i)
        L[i] = arr[l + i];
    for (int j=0; j<n2; ++j)
        R[j] = arr[m + 1+ j];


    /* Merge the temp arrays */

    // Initial indexes of first and second subarrays
    int i = 0, j = 0;

    // Initial index of merged subarry array
    int k = l;
    while (i < n1 && j < n2)
    {
        if (L[i] <= R[j])
        {
            arr[k] = L[i];
            i++;
        }
        else
        {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    /* Copy remaining elements of L[] if any */
    while (i < n1)
    {
        arr[k] = L[i];
        i++;
        k++;
    }

    /* Copy remaining elements of R[] if any */
    while (j < n2)
    {
        arr[k] = R[j];
        j++;
        k++;
    }
}

}

Answer 1

You are making two basic mistakes:

• First of all the creation of threads, creating threads is expensive in terms of time, for this reason it is better to use a thread pool or the standard java api: ExecutorService.

• The other basic error is the number of threads you use, when you are making recursive calls, you are increasing the number of threads in your processor constantly, you must to realise that from a certain number of threads, the work is not really parallelized, because the processor does not have enough cores to execute this work at the same time, however the overload introduced by multithreaded management does penalize performance.

This answer could help you understand how to take advantage of the multithread: Multithreaded merge sort, adding additional threads

Answer 2

Rather than dynamically creating threads, split the array into k chunks, then use k threads to sort each of the k chunks, then merge the sorted chunks as each thread completes it's task. The merging can also be multi-threaded. Say you use 4 chunks, and use 4 threads. Each thread 0,1,2,3 sorts its' chunk. Thread 1 and 3 terminate once their chunk is sorted. After thread 2 sorts it's chunk, it waits for thread 3 to complete and then merges chunks 2 and 3. After thread 0 sorts it's chunk, it waits for thread 1 to complete and then merges chunks 0 and 1, then waits for thread 2 to complete and then merges the merged 0+1 chunk with the merged 2+3 chunk.