归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路[归并].
算法描述
把长度为n的输入序列分成两个长度为n/2的子序列；
对这两个子序列分别采用归并排序；
将两个排序好的子序列合并成一个最终的排序序列。
归并操作
归并操作(merge)，也叫归并算法，指的是将两个顺序序列合并成一个顺序序列的方法。
设有数列{6，202，100，301，38，8，1}
初始状态：6,202,100,301,38,8,1
第一次归并后：{6,202},{100,301},{8,38},{1}，比较次数：3；
第二次归并后：{6,100,202,301}，{1,8,38}，比较次数：4；
第三次归并后：{1,6,8,38,100,202,301},比较次数：4；
总的比较次数为：3+4+4=11；
逆序数为14；
归并操作的原理
第一步：申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
第二步：设定两个指针，最初位置分别为两个已经排序序列的起始位置
第三步：比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
重复步骤3直到某一指针超出序列尾
将另一序列剩下的所有元素直接复制到合并序列尾
代码实现
public class MergeSort {
private static int count = 1;
public static void main(String[] args) {
int[] arr = {8, 4, 5, 7, 1, 3, 6, 2, 9, 10};
int[] temp = new int[arr.length];
split(arr, 0, arr.length - 1, temp);
System.out.println(Arrays.toString(arr));
}
/**
* 递归拆分数组然后合并
*
* @param arr 待拆分数组
* @param left 数组左边下标
* @param right 数组右下标
* @param temp 用于存放合并后的有序序列的数组
*/
public static void split(int[] arr, int left, int right, int[] temp) {
if (left >= right) {
return;
}
System.out.println("拆分第"+(count++)+"次");
int mid = left + (right - left) / 2;
//向左拆分
split(arr, left, mid, temp);
//向右拆分
split(arr, mid + 1, right, temp);
//每次拆分后都执行合并
merge(arr, left, mid, right, temp);
}
/**
* 合并两个各自有序序列(以mid为界)
*
* @param arr 原始数组
* @param left 数组左边下标
* @param mid 数组中间下标
* @param right 数组右边下标
* @param temp 用于存放新的有序数组
*/
public static void merge(int[] arr, int left, int mid, int right, int[] temp) {
int i = left;
int j = mid + 1;
//temp中的原始下标
int t = 0;
while (i <= mid && j <= right) {
//两边数组都没有比较完 继续
if (arr[i] < arr[j]) {
//左边数组中值更小
temp[t] = arr[i];
i++;
} else {
//右边数组中值更小
temp[t] = arr[j];
j++;
}
t++;
}
//有一边已经全部复制到temp中了
if (i <= mid) {
//左边还没有复制完，将左边全部元素复制到temp中
while (i <= mid) {
temp[t] = arr[i];
i++;
t++;
}
} else if (j <= right) {
//右边还没有复制完，将右边全部元素复制到temp中
while (j <= right) {
temp[t] = arr[j];
j++;
t++;
}
}
//将temp复制到原arr中
t = 0;
while (left <= right) {
arr[left] = temp[t];
left++;
t++;
}
}
}
复杂度
归并排序把集合一层一层进行折半分组。如果集合长度是n，那么折半的层数就是logn，每一层进行归并操作的运算量是n。所以归并排序的时间复杂度等于每一层的运算量乘以层级数，即O(nlogn)=。
我们再看空间复杂度，由于每次归并所创建的的额外集合都会随着方法的结束而被释放，因此这部分空间不应该累计，单次归并操作开辟的最大的空间是n，所以归并排序的空间复杂度是O(n)。
总结
归并排序的执行原理，主要分为以下步骤：
1.递归的方式进行拆分，将大的数组拆分成小的数组，直到剩余一个不能拆分
2.回溯的时候进行合并，合并时以mid为界，左右两边各自有序，通过额外的空间temp数组，将两个有序数组合并到一个有序数组中
3.将合并后的数组复制到原数组中，当回溯完成时整个数组有序
