Realize worker-threads for merge sort algorithm

Question

I have a single-thread version of the merge sort http://pastebin.com/2uMGjTxr

It creates an array, fills it with random numbers and calles the sort method on it that performs the merge sort:

private static int[] sort(int[] array) {
    //TODO: use multiple threads to speed up the sorting

    return mergeSort(array, 0, array.length);
}

Now I want to increase performance using the multithreading technique in java. The code is from my tutor and he said I have to add something to the sort method but that actually confuses me.

The merge sort is a devide and conquer algorithm:

• If the list is of length 0 or 1, then it is already sorted. Otherwise:
• Divide the unsorted list into two sublists of about half the size.
• Sort each sublist recursively by re-applying the merge sort.
• Merge the two sublists back into one sorted list.

So I actually would start a thread for each sublist. What do you think? How can merge sort be parallelized according to the give implementation? Has anyone a clue why I should edit the sort method?

Answer 1

This is a great exercise for the use of the ForkJoin Framework set to release in Java 7.0. Its exactly what you are looking for. You simply submit(fork) Recursive merging tasks to the pool and join the results when complete.

You can download the JSR 166 Binary. For more information this is a nice article

Edit to address your comment:

If you wanted to implement it yourself, you would not want a new Thread for each sublist. You can imagine there will be many partitions of a given array to sort so a thread per partition would grow huge (assuming a big enough array). Instead you would want a thread for each partitioned array you will actually being doing the merge work on. The ForkJoin does this for you, one of the benefits of using an FJ pool is that it will reuse threads instead of creating a new thread for a subprocess merge.