归并排序（Merge Sort）：是建立在归并操作上的一种有效，稳定的排序算法，该算法是采用分治法的一个非常典型的应用。

算法思路

• 把长度为n的输入序列分成两个长度为n/2的子序列；
• 对这两个子序列分别采用归并排序；
• 将两个排序好的子序列合并成一个最终的排序序列。

package sort;

import java.util.Arrays;

public class MergeSort {
	public static void main(String[] args) {
		int[] arr = { 8, 4, 5, 7, 1, 3, 6, 2 };
        //辅助数组
		int[] temp = new int[arr.length];
		mergeSort(arr, temp, 0, arr.length - 1);
		System.out.println(Arrays.toString(arr));
	}
	public static void mergeSort(int[] arr,int[] temp,int low,int high) {
		if(low<high) {
			int mid = (low+high)/2;
			mergeSort(arr, temp, low, mid); // 1. 对左边进行归并排序
			mergeSort(arr, temp, mid+1, high);   // 2. 对右边进行归并排序
			merge(arr,temp,low,mid,high);   // 3. 合并左右两个有序集合
		}
	}
	public static void merge(int[] arr,int[] temp,int low,int mid,int high) {
		int i = low;
		int j = mid +1;
		int k = 0;
		while(i<=mid&&j<=high) {
			if(arr[i]<=arr[j]) {
				temp[k++] = arr[i++];
			}else {
				temp[k++] = arr[j++];
			}
		}
		while(i<=mid) {   // 左边有剩余，将左边剩余的填入temp
			temp[k++] = arr[i++];
		}
		while(j<=high) {  // 右边有剩余，将右边剩余的填入temp
			temp[k++] = arr[j++];
		}
		k = 0;
		while(low<=high) {
			arr[low++] = temp[k++];
		}
	}
}