https://baike.baidu.com/item/%E5%BD%92%E5%B9%B6%E6%8E%92%E5%BA%8F

示例来源见链接.

归并操作(merge)，也叫归并算法，指的是将两个顺序序列合并成一个顺序序列的方法。

算法描述：

第一步：申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
第二步：设定两个指针，最初位置分别为两个已经排序序列的起始位置
第三步：比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
重复步骤3直到某一指针超出序列尾
将另一序列剩下的所有元素直接复制到合并序列尾

数列初始状态：{6，202，100，301，38，8，1}

算法细化过程如下：

第一次比较

分组：{6,202},{100,301},{38,8},{1}

比较每组数据：{6,202},{100,301},{8,38},{1}，共比较3次

第二次比较

申请合并组需要的空间、顺序比较每组字符，归并到新组，共比较4次：

{x,202},{100,301},{x,x},{x} -> {6, x, x, x},{1, 8, 38}，比较2次（6 vs 100，1 vs 8）

发现逆序对：{8,1},{38,1}，当前最长逆序对为{38,1}

{x,202},{x,301},{x,x},{x} -> {6, 100, x, x},{1, 8, 38}，比较1次（100 vs 202）

发现逆序对：{202,100}，当前最长逆序对为{202,100}

{x,x},{x,x},{x,x},{x} -> {6, 100, 202, 301},{1, 8, 38}，比较1次（202 vs 301）

未发现新的逆序对

第三次比较

申请合并新组需要的空间，顺序比较每组字符，归并到新组，共比较4次：

{6, 100, 202, 301},{x, 8, 38} -> {1, x, x, x, x, x, x}，比较1次（6 vs 1）

发现新的逆序对{6,1},{100,1},{202,1},{301,1}，当前最长逆序对：{301,1}

{x, 100, 202, 301},{x, 8, 38} -> {1, 6, x, x, x, x, x}，比较1次（6 vs 8）

未发现新的逆序对

{x, 100, 202, 301},{x, x, 38} -> {1, 6, 8, x, x, x, x}，比较1次（8 vs 100）

发现逆序对：{100,8},{202,8},{301,8}，当前最长逆序对：{301,1}

{x, 100, 202, 301},{x, x, x} -> {1, 6, 8, 38, x, x, x}，比较1次（38 vs 100）

发现逆序对：{100,38},{202,38},{301,38}，当前最长逆序对：{301,1}

java代码：

    static int[] mergeSort(int[] arr, int l, int r){
        if(l == r){
            return new int[] { arr[l] };
        }
        int middle = l + (r - l) / 2;
        int[] leftArr = mergeSort(arr, l, middle);
        int[] rightArr = mergeSort(arr, middle + 1, r);
        int[] mergeArr = new int[leftArr.length + rightArr.length];

        int mergeIndex = 0, leftIndex = 0, rightIndex = 0;
        while(leftIndex < leftArr.length && rightIndex < rightArr.length){
            mergeArr[ mergeIndex ++ ] = leftArr[leftIndex] <= rightArr[rightIndex] ? leftArr[leftIndex ++] : rightArr[rightIndex ++];
        }
        while(leftIndex < leftArr.length){
            mergeArr[ mergeIndex ++ ] = leftArr[leftIndex ++];
        }
        while(rightIndex < rightArr.length){
            mergeArr[ mergeIndex ++ ] = rightArr[rightIndex ++];
        }
        System.out.println(Arrays.toString(mergeArr));
        return mergeArr;
    }

    public static void main(String[] args) {
        int[] arr = {6, 202, 100, 301, 38, 8, 1};
        System.out.println(Arrays.toString(arr) + " - start");
        arr = mergeSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr) + " - end");
    }

输出：

[6, 202, 100, 301, 38, 8, 1] - start
[6, 202]
[100, 301]
[6, 100, 202, 301]
[8, 38]
[1, 8, 38]
[1, 6, 8, 38, 100, 202, 301]
[1, 6, 8, 38, 100, 202, 301] - end