基本思想：
将两个或两个以上的有序表合并成一个有序表的过程。常用的归并为2-路归并，就是将两个有序表合为一个有序表。
过程：
先来看一张示意图：
可以看出，归并排序分为分解和合并两个步骤。
分解就是将原数组分解成只有一个数的数组。
合并就是将相邻两个数组进行排序合并。
代码实现：
import java.util.Arrays;public class MergingSort {public static void main(String[] args) {int[] a={1,6,2,8,0,3,4,5,7};Sort(a);}private static void Sort(int[] s){int len = s.length;int[] temp = new int[len];Merge(s,0,len-1,temp);System.out.println(Arrays.toString(s));}private static void Merge(int[] s,int low,int high,int[] temp){if(low<high){//递归结束条件：分解直到数组长度不小于1//递归分解int mid=(low+high)/2;Merge(s, low, mid, temp);//左子数组Merge(s, mid+1, high, temp);//右子数组if (s[mid]>s[mid+1]) {//如果左子数组最大的数都不大于右子数组最小数，数组已经有序，不需要进行排序//将无序数组赋给tempfor (int i = low; i <= high; i++) {temp[i] = s[i];}//给无序数组排序，并赋给原数组。int i = low;//左子数组起点int j = mid + 1;//右子数组起点for (int k = low; k <= high; k++) {//k为原数组赋值点if (i == mid + 1) {//如果i下标已经到了右子数组起点，说明左子数组已经比较完毕s[k] = temp[j];//只需要将右子数组剩下的全部值赋给原数组即可j++;//j标签向前移动} else if (j == high + 1) {//同上s[k] = temp[i];i++;} else if (temp[i] < temp[j]) {//如果左子数组最小值[i]小于右子数组最小值[j]s[k] = temp[i];//将[i]作为两个子数组中的最小值赋给原数组i++;//i下标向前移动} else {//同上s[k] = temp[j];j++;}}}}}}
结果：
时间复杂度：
空间复杂度：
算法特点：
(1)：稳定排序。
(2)：可适用于大多数情况的排序。
