归并排序

• 算法思想
  归并排序中使用分治法。将原来的问题划分成子问题，然后递归求解子问题，然后再合并这些子问题的解。
• 时间复杂度
  归并排序无论什么情况都是O(nlgn)
  可以理解为每个要归并排序的数组大致会被分成lgn层。每一层都有n个元素
  例如归并排序数组

int[] num = {32,2,1,6,23,11,10,43,2};

最开始通过数组下标low=0和长度high=8找到中间值mid=(low+high)/2。此时把原问题分解成2个子问题，然后再对两个子问题进行归并排序。先把0-mid子数组排序，然后mid+1-high排序

public static int[] mergeSort(int[] num,int low,int high) {
        
        int mid = (low+high)/2;
        if (low<high) {
            mergeSort(num, low, mid);
            
            mergeSort(num, mid+1, high);
            
            mergeSort( num, low, mid,high);
        }
        return num; 
    }

    private static void mergeSort(int[] num, int low, int mid, int high) {

        int[] temp = new int[high-low+1];
        int i=low;
        int j=mid+1;
        int k=0;
        while(i<=mid&&j<=high){
            if (num[i]<num[j]) {
                temp[k++]=num[i++];
            }else {
                temp[k++]=num[j++];
            }
        }
        while(i<=mid){
            temp[k++]=num[i++];
        }
        while(j<=high){
            temp[k++]=num[j++];
        }
        
        for (int k2 = 0; k2 < temp.length; k2++) {
            num[k2+low]=temp[k2];
        }
    }