Geek asks and answers

Implement workflows for merge sort algorithm

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

It creates an array, fills it with random numbers, and calls the sort method on it, which 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 method in java. The code is from my mentor, and he said that I need to add something to the sorting method, but that really bothers me.

Merge sorting is an algorithm of division and subjugation:

  • If the list has a length of 0 or 1, then it is already sorted. Otherwise:
  • Divide the unsorted list into two sub-lists by about half.
  • Sort each sublister recursively, reapplying merge sort.
  • .

, . ? ? - , ?

+3
2

ForkJoin Framework, Java 7.0. , . (fork) .

JSR 166 Binary. this

, :

, . , , ( , ). , . ForkJoin , FJ , .

+4

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

More articles:


All Articles