归并操作（merge），也叫归并算法，指的是将两个已经排序的序列合并成一个序列的操作。
归并排序算法依赖归并操作。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
归并排序在众多排序算法中既是稳定排序，效率也比较高，同时，归并排序不仅可以用于内排序，还可以用于外排序。
1.两个有序数列的合并
设两个有序数列放在同一向量中相邻的位置上：R[low..m]，R[m+1..high]，先将它们合并到一个局部的暂存向量 R1中，待合并完成后将 R1 复制回 R[low..high]中。
（1）合并过程
合并过程中，设置 i，j 和 p 三个指针，其初值分别指向这三个记录区的起始位置。
合并时依次比较 R[i]和 R[j]的关键字，取关键字较小的记录复制到 R1[p]中，然后将被复制记录的指针 i 或 j 加 1，以及指向复制位置的指针 p 加 1。
重复这一过程直至两个输入的子文件有一个已全部复制完毕，此时将另一非空的子文件中剩余记录依次复制到 R1 中即可。
（2）动态申请 R1
实现时，R1 是动态申请的，因为申请的空间可能很大，所以在工程上应用时，可能需要加入申请空间是否成功的处理。
2.归并排序的实现
（1）二路归并的思路
将数组划均分为两个子数组；
对两个字数组进行排序；
将排序好的两个字数组归并。
所谓 N路归并 是指将数组均分为N个子数组，将字数组排序后再归并。二路归并是归并排序的最一般的情况。
（2）归并排序实现的一般化过程
申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
设定两个指针，最初位置分别为两个已经排序序列的起始位置
比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
重复步骤3直到某一指针到达序列尾
将另一序列剩下的所有元素直接复制到合并序列尾
（3）实现过程
public class MergeSort {
public static void main(String[] args){
int[] arr=new int[]{8,7,6,5,4,3,2,1};
for(int i=0;i<arr.length;i++){
System.out.print(arr[i]+",");
}
//想起引用传递和值传递的问题，数组是引用传递，不需要什么返回值
sort(arr,arr.length);
System.out.println("排序后");
for(int i=0;i<arr.length;i++){
System.out.print(arr[i]+",");
}
}
public static void sort(int[] arr,int n){
if(arr==null || n<2){
return;//边界情况
}
divide(arr,0,n-1);
}
/**
*
* @param arr 待排序数组
* @param left 待排序区间左侧下标
* @param right 待排序区间右侧下标
*/
public static void divide(int[] arr,int left,int right){
if(left>=right){
return;
}
int m=(left+right)/2;//从中间开始分成两个区间进行归并
divide(arr,left,m);//一直递归划分直到区间长度为1
divide(arr,m+1,right);
//开始逐级往上进行归并操作
binaryMerge(arr,left,m,right);//第一次进行merge操作的递归栈最深层此时是merge(arr,0,0,1)
}
/**
* 对数组arr[left...right]位置进行递归的归并排序
* @param arr
* @param left
* @param rigtht
* @param temp
*/
public static void binaryMerge(int[] arr,int left,int m,int right){
/**
* 归并排序的时间复杂度为O(n),指的就是最大长度为n的临时数组
*/
int[] temp=new int[right-left+1];
int l=left;//
int r=m+1;//
int index=0;//
while(l<=m && r<=right){
if(arr[l]<arr[r]){
temp[index]=arr[l];
index++;
l++;
}else{
temp[index]=arr[r];
index++;
r++;
}
}
/**
* 交换完了如果哪一侧数组还有剩余，则全部赋值
* 实际的一次归并下面的两个while循环只会执行一个
* warn!不要漏了等于的情况！否则会每两个元素丢失一个元素
*/
while(l<=m){
temp[index]=arr[l];
index++;
l++;
}
while(r<=right){
temp[index]=arr[r];
index++;
r++;
}
/**
* 用临时数组的部分排序的序列全部替换待排序数组中对应的部分
* 这里应该用temp.length，不能用arr.length
*/
for(int i=0;i<temp.length;i++){
//注意是left，此时的l是已经变化了的
arr[left+i]=temp[i];
}
}
}
（4）时间和空间复杂度
归并排序的最好、最坏和平均时间复杂度都是O(nlogn)，而空间复杂度是O(n)，
比较次数介于(nlogn)/2和(nlogn)-n+1，赋值操作的次数是(2nlogn)。因此可以看出，归并排序算法比较占用内存，但却是效率高且稳定的排序算法。
3.空间复杂度为O(1)的归并排序
归并排序的空间复杂度为O(N)，
通过优化可以把空间复杂度降为O(1)，通过手摇算法，
但实际上通过手摇算法后，此时的时间复杂度会上升。
4.多路归并排序
归并排序的思想可以用于外排序。
外排序是相对内排序而言的，在常规的小规模排序过程中，都是直接在内存中对数据进行排序处理的，而对于数据量极大的排序问题，这种方式是不现实的。
这个时候就要通过外排序来进行，先将数据划分成多个规模能在内存中处理的子集，对各个子集排序后存放在临时的磁盘文件上，然后再将这些子集归并到输出文件中。
这个过程要使用到多路归并。