对工作/临时数组进行一次分配，并避免在合并期间复制数据(除非将剩余的单个运行从一个数组移动到另一个数组).

Do a single allocation of the working/temp array and avoid copying of data during merge (unless moving a single remaining run from one array to the other).

自下而上的归并排序示例.

Bottom up merge sort example.

package jsortbu;
import java.util.Random;

public class jsortbu {
    static void MergeSort(int[] a)          // entry function
    {
        if(a.length < 2)                    // if size < 2 return
            return;
        int[] b = new int[a.length];
        BottomUpMergeSort(a, b);
    }

    static void BottomUpMergeSort(int[] a, int[] b)
    {
    int n = a.length;
    int s = 1;                              // run size 
        if(1 == (GetPassCount(n)&1)){       // if odd number of passes
            for(s = 1; s < n; s += 2)       // swap in place for 1st pass
                if(a[s] < a[s-1]){
                    int t = a[s];
                    a[s] = a[s-1];
                    a[s-1] = t;
                }
            s = 2;
        }
        while(s < n){                       // while not done
            int ee = 0;                     // reset end index
            while(ee < n){                  // merge pairs of runs
                int ll = ee;                // ll = start of left  run
                int rr = ll+s;              // rr = start of right run
                if(rr >= n){                // if only left run
                    do{                     //   copy it
                        b[ll] = a[ll];
                        ll++;
                    }while(ll < n);
                    break;                  //   end of pass
                }
                ee = rr+s;                  // ee = end of right run
                if(ee > n)
                    ee = n;
                Merge(a, b, ll, rr, ee);
            }
            {                               // swap references
                int[] t = a;
                a = b;
                b = t;
            }
            s <<= 1;                        // double the run size
        }
    }

    static void Merge(int[] a, int[] b, int ll, int rr, int ee) {
        int o = ll;                         // b[]       index
        int l = ll;                         // a[] left  index
        int r = rr;                         // a[] right index
        while(true){                        // merge data
            if(a[l] <= a[r]){               // if a[l] <= a[r]
                b[o++] = a[l++];            //   copy a[l]
                if(l < rr)                  //   if not end of left run
                    continue;               //     continue (back to while)
                while(r < ee){              //   else copy rest of right run
                    b[o++] = a[r++];
                }
                break;                      //     and return
            } else {                        // else a[l] > a[r]
                b[o++] = a[r++];            //   copy a[r]
                if(r < ee)                  //   if not end of right run
                    continue;               //     continue (back to while)
                while(l < rr){              //   else copy rest of left run
                    b[o++] = a[l++];
                }
                break;                      //     and return
            }
        }
    }

    static int GetPassCount(int n)          // return # passes
    {
        int i = 0;
        for(int s = 1; s < n; s <<= 1)
            i += 1;
        return(i);
    }

    public static void main(String[] args) {
        int[] a = new int[10000000];
        Random r = new Random();
        for(int i = 0; i < a.length; i++)
            a[i] = r.nextInt();
        long bgn, end;
        bgn = System.currentTimeMillis();
        MergeSort(a);
        end = System.currentTimeMillis();
        for(int i = 1; i < a.length; i++){
            if(a[i-1] > a[i]){
                System.out.println("failed");
                break;
            }
        }
        System.out.println("milliseconds " + (end-bgn));
    }
}

自顶向下合并排序示例.一对相互递归的函数用于避免复制操作.合并的方向基于递归级别.Merge() 对于自下而上和自上而下都是相同的.

Top down merge sort example. A pair of mutually recursive functions are used to avoid copy back operations. The direction of merge is based on the level of recursion. Merge() is the same for both bottom up and top down.

package jsorttd;
import java.util.Random;

public class jsorttd {
    static void MergeSort(int[] a)          // entry function
    {
        if(a.length < 2)                    // if size < 2 return
            return;
        int[] b = new int[a.length];
        MergeSortAtoA(a, b, 0, a.length);
    }

    static void MergeSortAtoA(int[] a, int[] b, int ll, int ee)
    {
        if(ee - ll > 1) {
            int rr = (ll + ee)>>1;          // midpoint, start of right half
            MergeSortAtoB(a, b, ll, rr);
            MergeSortAtoB(a, b, rr, ee);
            Merge(b, a, ll, rr, ee);        // merge b to a
        }
    }

    static void MergeSortAtoB(int[] a, int[] b, int ll, int ee)
    {
        if(ee - ll > 1) {
            int rr = (ll + ee)>>1;          //midpoint, start of right half
            MergeSortAtoA(a, b, ll, rr);
            MergeSortAtoA(a, b, rr, ee);
            Merge(a, b, ll, rr, ee);        // merge a to b
        } else if((ee - ll) == 1) {         // if just one element
            b[ll] = a[ll];                  //   copy a to b
        }
    }

    static void Merge(int[] a, int[] b, int ll, int rr, int ee) {
        int o = ll;                         // b[]       index
        int l = ll;                         // a[] left  index
        int r = rr;                         // a[] right index
        while(true){                        // merge data
            if(a[l] <= a[r]){               // if a[l] <= a[r]
                b[o++] = a[l++];            //   copy a[l]
                if(l < rr)                  //   if not end of left run
                    continue;               //     continue (back to while)
                while(r < ee){              //   else copy rest of right run
                    b[o++] = a[r++];
                }
                break;                      //     and return
            } else {                        // else a[l] > a[r]
                b[o++] = a[r++];            //   copy a[r]
                if(r < ee)                  //   if not end of right run
                    continue;               //     continue (back to while)
                while(l < rr){              //   else copy rest of left run
                    b[o++] = a[l++];
                }
                break;                      //     and return
            }
        }
    }

    public static void main(String[] args) {
        int[] a = new int[10000000];
        Random r = new Random();
        for(int i = 0; i < a.length; i++)
            a[i] = r.nextInt();
        long bgn, end;
        bgn = System.currentTimeMillis();
        MergeSort(a);
        end = System.currentTimeMillis();
        for(int i = 1; i < a.length; i++){
            if(a[i-1] > a[i]){
                System.out.println("failed");
                break;
            }
        }
        System.out.println("milliseconds " + (end-bgn));
     }
}

这两种方法在我的系统(Win 7、Intel 3770K 3.5 ghz、NetBeans 8.1、Java 1.8.0_65-b17)上对 1000 万个整数进行排序都需要大约 1 秒的时间.

Both methods take about 1 second to sort 10 million integers on my system (Win 7, Intel 3770K 3.5 ghz, NetBeans 8.1, Java 1.8.0_65-b17).