一：归并排序的思想

归并排序（Merge Sort）

当我们要排序这样一个数组的时候，归并排序法首先将这个数组分成一半。如图：

然后想办法把左边的数组给排序，右边的数组给排序，之后呢再将它们归并起来。当然了当我们对左边的数组和右边的素组进行排序的时候，再分别将左边的数组和右边的数组分成一半，然后对每一个部分先排序，再归并。如图：对于上面的每一个部分呢，我们依然是先将他们分半，再归并，如图：

分到一定细度的时候，每一个部分就只有一个元素了，那么我们此时不用排序，对他们进行一次简单的归并就好了。如图：归并到上一个层级之后继续归并，归并到更高的层级，如图：直至最后归并完成。

二：归并排序代码

package totoSort;import java.util.Arrays;public class Msort {public static void main(String[] args) {int[] arrays = new int[] {1,5,4,3,2};sort(arrays,0,arrays.length - 1);System.out.print(Arrays.toString(arrays));}public static void sort(int[] arr, int left, int right) {int[] temp = new int[arr.length];if(left >= right) {return;}int mid = (left + right)/2; // 2sort(arr,left,mid); sort(arr, mid + 1, right);int i = left;int j = mid + 1;int t = 0;while(i <= mid && j <= right) {if(arr[i] <= arr[j]) {temp[t] = arr[i];i++;t++;}else {temp[t] = arr[j];j++;t++;}}while(i <= mid) {temp[t] = arr[i];i++;t++;}while(j <= right) {temp[t] = arr[j];j++;t++;}int k = 0;int tempIndex = left;while(tempIndex <= right) {arr[tempIndex] = temp[k];k++;tempIndex++;}}
}