public class MergeSort {
    public static void main(String[] args) {
        int[] toBeSorted = { 1, 3, 5, 2, 4, 6 };
        mergeSort(0, toBeSorted.length - 1, toBeSorted);
        for (int p = 0; p < toBeSorted.length; p++) {
            System.out.print(toBeSorted[p]);
        }
        System.out.println();
    }

    public static void mergeArray(int s, int e, int[] toBeMerge) {
        int[] t = new int[toBeMerge.length];
        int f = 0;
        int mid = (s + e) / 2;
        int s1 = s, e1 = mid;
        int s2 = mid + 1, e2 = e;
        while (s1 <= e1 && s2 <= e2) {
            t[f++] = (toBeMerge[s1] <= toBeMerge[s2]) ? toBeMerge[s1++] : toBeMerge[s2++];
        }
        while (s1 <= e1) {
            t[f++] = toBeMerge[s1++];
        }
        while (s2 <= e2) {
            t[f++] = toBeMerge[s2++];
        }

        for (int i = s; i < f; i++) {
            toBeMerge[i] = t[i];
        }
    }

    public static void mergeSort(int s, int e, int[] toBSorted) {
        if (e > s) {
            int mid = (s + e) / 2;
            mergeSort(s, mid, toBSorted);
            mergeSort(mid + 1, e, toBSorted);
            mergeArray(s, e, toBSorted);
        }
    }
}

时间复杂度的计算：

因为是递归的算法，所以可以这样算,

T(n)=段数*每段的时间复杂度+合并的时间复杂度=2T(n/2)+O(n)

∵lgab=lg22=1 和合并的时间复杂度的幂相等

∴T(n)=nlgn