归并排序运用分治的思想，把大的问题逐部分解成能够解决的小问题.
时间复杂度为nlogn.
Ps:使用引用传递的方法把临时数组赋值进去，这样就可以没必要每次都生成一个新的数组.
代码：
/**
* Created by Hammy on 2018/3/1.
*/
public class MergeSort
{
/**
* 二路归并排序
*/
public static void sort(int[] array){
int[] tempArray = new int[array.length];
mergeSort(array,tempArray,0,array.length-1);
}
private static void mergeSort(int[] array,int[] tempArray,int left,int right){
if(left>=right)
return;
int mid=left+((right-left)>>1);
mergeSort(array,tempArray,left,mid);
mergeSort(array,tempArray,mid+1,right);
merge(array,tempArray,left,mid,right);
}
private static void merge(int[] array,int[] tempArray,int left,int mid,int right){
int tempIndex = left;
int copyIndex = left;
int rightStart = mid+1;
while(left<=mid&&rightStart<=right){
if(array[left]<array[rightStart]){
tempArray[tempIndex++]=array[left++];
}else{
tempArray[tempIndex++]=array[rightStart++];
}
}
while(left<=mid)
tempArray[tempIndex++]=array[left++];
while(rightStart<=right)
tempArray[tempIndex++]=array[rightStart++];
//开始复制
while(copyIndex<=right){
array[copyIndex]=tempArray[copyIndex++];
}
}
