CODEWITHSUNDEEP
javamultithreadingmergesort
DarkLeafyGreen
DarkLeafyGreen

Reputation: 70416

Realize worker-threads for merge sort algorithm

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:

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?

Upvotes: 3

Views: 797

Answers (2)

KaviK
KaviK

Reputation: 625

Use RecursiveAction class in java 7

public class ParallelMergeSort {

private static final ForkJoinPool threadPool = new ForkJoinPool();
private static final int SIZE_THRESHOLD = 16;

public static void sort(Comparable[] a) {
    sort(a, 0, a.length-1);
}

public static void sort(Comparable[] a, int lo, int hi) {
    if (hi - lo < SIZE_THRESHOLD) {
        insertionsort(a, lo, hi);
        return;
    }

    Comparable[] tmp = new Comparable[a.length];
    threadPool.invoke(new SortTask(a, tmp, lo, hi));
}

/**
 * This class replaces the recursive function that was
 * previously here.
 */
static class SortTask extends RecursiveAction {
    Comparable[] a;
    Comparable[] tmp;
    int lo, hi;
    public SortTask(Comparable[] a, Comparable[] tmp, int lo, int hi) {
        this.a = a;
        this.lo = lo;
        this.hi = hi;
        this.tmp = tmp;
    }

    @Override
    protected void compute() {
        if (hi - lo < SIZE_THRESHOLD) {
            insertionsort(a, lo, hi);
            return;
        }

        int m = (lo + hi) / 2;
        // the two recursive calls are replaced by a call to invokeAll
        invokeAll(new SortTask(a, tmp, lo, m), new SortTask(a, tmp, m+1, hi));
        merge(a, tmp, lo, m, hi);
    }
}

private static void merge(Comparable[] a, Comparable[] b, int lo, int m, int hi) {
    if (a[m].compareTo(a[m+1]) <= 0)
        return;

    System.arraycopy(a, lo, b, lo, m-lo+1);

    int i = lo;
    int j = m+1;
    int k = lo;

    // copy back next-greatest element at each time
    while (k < j && j <= hi) {
        if (b[i].compareTo(a[j]) <= 0) {
            a[k++] = b[i++];
        } else {
            a[k++] = a[j++];
        }
    }

    // copy back remaining elements of first half (if any)
    System.arraycopy(b, i, a, k, j-k);

}

private static void insertionsort(Comparable[] a, int lo, int hi) {
    for (int i = lo+1; i <= hi; i++) {
        int j = i;
        Comparable t = a[j];
        while (j > lo && t.compareTo(a[j - 1]) < 0) {
            a[j] = a[j - 1];
            --j;
        }
        a[j] = t;
    }
} }

Upvotes: 0

John Vint
John Vint

Reputation: 40256

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.

Upvotes: 4

Related Questions