归并排序运用分治的思想，把大的问题逐部分解成能够解决的小问题.
时间复杂度为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++];
        }
    }