5.归并排序(稳定排序）

由于归并排序是平均分割子序列，所以最好、最坏、平均时间复杂度都是 O(nlogn), 属于稳定排序
从代码不难看出：归并排序的空间复杂度是 O(n/2 + logn) = O(n)

private T[] leftArray;
    @Override
    protected void sort() {
        leftArray = (T[]) new Comparable[(array.length >> 1)];
        sort(0, array.length);
    }
    private void sort(int begin, int end) {
        if (end - begin < 2) {
            return;
        }
        int mid = (begin + end) >> 1;
        sort(begin, mid);
        sort(mid, end);
        merge(begin, mid, end);
    }
    /**
     * 将[begin, mid] 和 [mid, end) 范围的序列合并成一个有序序列
     */
    private void merge(int begin, int mid, int end) {
        int li = 0, le = mid - begin;
        int ri = mid, re = end;
        int ai = begin;
        //将左边数组存进leftArray中
        for (int i = li; i < le; i++) {
            leftArray[i] = array[begin + i];
        }
        //就可以开始进行挪动元素了
        while (li < le) {
            if (ri < re && cmp(array[ri], leftArray[li]) > 0) {
                array[ai++] = array[ri++];
            }else {
                array[ai++] = leftArray[li++];
            }
        }
    }

迭代版：

public static void merge_sort(int[] arr) {
        int[] nums = new int[arr.length];
        for (int i = 1; i < arr.length; i++) {
            for (int j = 0; j < arr.length; j += i * 2) {
                int low = j, mid = Math.min(i + j, arr.length), high = Math.min(j + i * 2, arr.length);
                int k = low;
                int start1 = low, end1 = mid;
                int start2 = mid, end2 = high;
                while (start1 < end1 && start2 < end2) {
                    nums[k++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++];
                }
                while (start1 < end1) {
                    nums[k++] = arr[start1++];
                }
                while (start2 < end2) {
                    nums[k++] = arr[start2++];
                }
            }
            int[] temp = arr;
            arr = nums;
            nums = temp;
        }
        nums = arr;
    }