Recursive merge sort, using a temporary array

public void mergesort(int[] a, int[] b, int left, int right) {
    if (left < right) {
        int mid = (left + right) >> 1;
        mergesort(a, b, left, mid);
        mergesort(a, b, mid + 1, right); merge(a, b, left, mid, right); }}Copy the code

Non-recursive implementation of merge sort (no stack)

public void mergesort(int[] a) {
    int[] b = new int[a.length];
    for (int i = 1; i <= a.length / 2; i <<= 1) {
        for (int j = 0; j + i < a.length; j += i * 2) {
            int left = j;
            int right = j + i * 2 - 1;
            int mid = j + i - 1;
            if (right > a.length - 1) {
                right = a.length - 1; } merge(a, b, left, mid, right); }}}Copy the code

ForkJoin implements merge sort

public void sort(int[] a) {
    ForkJoinPool forkJoinPool = new ForkJoinPool();
    forkJoinPool.invoke(new SortTask(a, 0, a.length - 1));
    forkJoinPool.shutdown();
}
private static class SortTask extends RecursiveAction {

    private int[] a;
    private int left;
    private int right;

    public SortTask(int[] a, int left, int right) {
        this.a = a;
        this.left = left;
        this.right = right;
    }

    @Override
    protected void compute(a) {
        int[] b = new int[a.length];
        if (left < right) {
            int mid = (left + right) >> 1;
            SortTask sortTask1 = new SortTask(a, left, mid);
            SortTask sortTask2 = new SortTask(a, mid + 1, right); sortTask1.fork(); sortTask2.fork(); sortTask1.join(); sortTask2.join(); merge(a, b, left, mid, right); }}public static void merge(int[] a, int[] b, int left, int mid, int right) {
        int i = left;
        int j = mid + 1;
        int t = 0;
        while (i<=mid && j<=right) {
            if (a[i] <= a[j]) {
                b[t++] = a[i++];
            } else{ b[t++] = a[j++]; }}while (i<=mid) {
            b[t++] = a[i++];
        }
        while (j<=right) {
            b[t++] = a[j++];
        }
        t = 0;
        while(left <= right) { a[left++] = b[t++]; }}}Copy the code

Merge two ordered portions of an array, using a temporary array

public void merge(int[] a, int[] b, int left, int mid, int right) {
    int i = left;
    int j = mid + 1;
    int t = 0;
    while (i <= mid && j <= right) {
         if (a[i] <= a[j]) {
             b[t++] = a[i++];
         } else{ b[t++] = a[j++]; }}while (i <= mid) {
        b[t++] = a[i++];
    }
    while (j <= right) {
        b[t++] = a[j++];
    }
    t = 0;
    while(left <= right) { a[left++] = b[t++]; }}Copy the code