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?

John Vint · Accepted Answer · 2011-05-06 16:32:14Z

4

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.

edited May 6, 2011 at 16:32

answered May 6, 2011 at 15:38

John Vint

40.3k7 gold badges81 silver badges109 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

DarkLeafyGreen Over a year ago

Nice hint. But actually I want my own implementation for that.

John Vint Over a year ago

@ArtWorkAD. You can use the framwork to implement it yourself. The article I linked was just to give you an idea on how the fork/join aspect worked.

John Vint Over a year ago

@ArtWorkAD however, for the sake of learning the implementation yourself I added an edit.

KaviK · Accepted Answer · 2017-01-24 11:52:46Z

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;
    }
} }

Collectives™ on Stack Overflow

Realize worker-threads for merge sort algorithm

2 Answers 2

3 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related