归并排序

归并排序的时间复杂度是O(nlogn)，优与选择排序以及冒泡排序，采用的思想就是分治思想，先分，将要排序的数组一分为二，然后再治，就是合并，下面直接从代码上看：

 private void mergeSort(int[] oriArray){
        int[] tempArray = new int[oriArray.length];
        mergeSort(oriArray, tempArray, 0, oriArray.length -1);
    }

    private void mergeSort(int[] oriArray, int[] tempArray, int left, int right){
        if (left < right){
            int center = (left + right )/2;
            mergeSort(oriArray, tempArray, left, center);
            mergeSort(oriArray, tempArray, center +1, right);
            merge(oriArray, tempArray, left, center + 1, right);
        }
    }

    private int[] merge(int[] oriArray, int[] tempArray, int leftStart, int rightStart, int rightEnd){
        int leftEnd = rightStart -1;
        int tempStart = leftStart;
        int totalNum = rightEnd - leftStart + 1;
        while (leftStart <= leftEnd && rightStart <= rightEnd){
            if (oriArray[leftStart] <= oriArray[rightStart]){
                tempArray[tempStart] = oriArray[leftStart];
                leftStart++;
            } else {
                tempArray[tempStart] = oriArray[rightStart];
                rightStart ++;
            }
            tempStart ++;
        }

        while (leftStart <= leftEnd ){
            tempArray[tempStart] = oriArray[leftStart];
            tempStart ++;
            leftStart ++;
        }

        while (rightStart <= rightEnd){
            tempArray[tempStart] = oriArray[rightStart];
            tempStart ++;
            rightStart ++;
        }

        //为什么用rightEnd赋值，因为在合并的过程中，rightEnd的值没有变化，rightEnd表示的数组位置也是原数组的数组位置。leftStart和rightStart是用来标记合并时的两个数组的位置的。
        for (int i = 0;i< totalNum;i++, rightEnd --){
            oriArray[rightEnd] = tempArray[rightEnd];
        }

        return oriArray;
    }

总之，归并排序就是先分后治，不断的递归调用直到两个元素的时候，再又一层一层的往上合并。