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
