归并排序使用的方法是分治法，即将问题分解为许多类似的小问题然后递归求解。 这里不做详细分析，直接看图解过程。
分的过程：可以直接除以二分割（这里总数是奇数也可以）。 治的过程：核心是合并两个有序的数组。
归并排序的核心就是治的过程也就是合并两个有序的数组。实现过程如下（以升序排序为例）：
两指针分别指向数组的头部，并构建一个长度是两个数组之和的临时数组，用于存储数据。两指针所在位置的值比较，将值小的填入临时数组中，其所在的指针后移一位。反复进行2步骤，直到有一个数组的指针越界，将另外一个数组的所有后续元素依次填入临时数组中，合并完成。图解： 以arr1 = {1，5，6}；arr2 ={3，7，9}为例。 左右比较，填入1，左边后移一位。 左右比较，填入3，右边后移一位。 左右比较，填入5，左边后移一位。 左右比较，填入6，左边后移一位。 指针越界，将右边元素依次填入。 合并完成。
代码： 下面代码中合并的是原始数组中arr[left 到 mid]段与arr[mid+1 到 right]段，故最后将临时数组temp中的元素拷贝会arr[left 到 right]段（因为整个排序过程是还在原始数组中进行的）。left，mid，right这是进行假想的分割，详细的分的过程后面的代码。
/** * 【合并】两个有序数组 * @param arr 总数组 * @param left 左数组开始指针（arr左指针） * @param mid 右数组开始指针 * @param right 右指针（arr右指针） */ public static void merge(int[] arr, int left, int mid, int right){ int[] temp = new int[right-left+1]; int l = left;//左数组初始索引 int m = mid + 1;//右数组初始索引 int t = 0;//临时数组初始索引 //1.将左右数组元素按规则填入temp数组中 while(l <= mid && m <= right){ if(arr[l] > arr[m]){ temp[t] = arr[m]; m++; t++; } else{ temp[t] = arr[l]; l++; t++; } } //2.将数组剩余元素填入temp中 if(l > mid){ while(m <= right){ temp[t] = arr[m]; m++; t++; } } else{ while(l <= mid ){ temp[t] = arr[l]; l++; t++; } } //3.将temp数组拷贝到arr中 t = 0; l = left; while(l <= right){ arr[l] = temp[t]; l++; t++; } }代码： 使用递归进行分割，然后使用merge方法合并数组。
public static void Sort(int[] arr, int left, int right){ if(left < right){ int mid = (left+right)/2;//取中间值 Sort(arr, left, mid);//分 Sort(arr, mid+1, right);//分 merge(arr, left, mid, right); //治 } }测试结果： [0, 4, 5, 5, 6, 8, 12, 12, 20, 65, 78, 87, 855]
