归并排序

闲来无事，总结一下排序算法，感觉快要忘光啦。

public static void mergeSort(int[] arr, int low,int high){
        if(low < high){
            int mid = low + (high - low)/2;
            mergeSort(arr,low,mid);
            mergeSort(arr,mid+1,high);
            merge(arr,low,mid,high);
        }
    }
    public static void merge(int[] arr, int low,int mid,int high){

        int[] temp = new int[high-low+1];
        int i = low,j = mid+1,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[k++] = arr[i++];
        }
        while(j <= high){
            temp[k++] = arr[j++];
        }
        for(k = 0;k<temp.length;k++){
            arr[low+k] = temp[k];//很容易出问题
        }
    }

对几个关键性质进行分析：

时间复杂度：
归并排序的时间复杂度为O(nlogn)。主要从两个方面进行分析：1.数组的划分 2.数组的有序归并。
对于一趟归并排序，会将数组中所有数字都扫描一遍，因此会耗费O(n)。归并排序过程类似一个完全二叉树，根据二叉树的性质，整个归并排序会进行logn次。因此总的时间复杂度为O(nlogn)。
对于长度为n的数组，需要进行logn次二路归并，每次归并时间为O(n)，因此最优时间复杂度和最差时间复杂度都为O(nlogn)。
空间复杂度：
空间复杂度为O(n)

稳定性：
归并排序是一种稳定的排序算法，因为存在if(arr[i] < arr[j])，在归并过程中不会改变元素的相对位置。

总结：
归并排序是一种比较占用内存，但是效率非常高并且稳定的排序算法。
在内部排序中不会使用该算法，外部排序才会考虑使用这种方法。