归并排序的描述

归并排序是将两个有序的数列合并成一个有序的数列。给定一个一维无序数组，递归拆分成两个子数组，直到每个子数组中只有一个元素，将两个子数组的两个元素合并为一个有序数列，再向上依次合并，最后整个数组有序。

归并排序的分析

归并排序是典型的以空间换时间的算法。额外的数组空间用来暂存排序的结果，时间复杂度是O(nlogn)，空间复杂度是O(n)。

如下图展示归并排序的过程：

归并排序的过程

在初始的无序数列中，PartA和PartB都是有序的部分，两者合并成一个更大的有序数列1，同样的无序数列其他部分（例如，PartC，PartD等）依次合并；多个有序的数列（有序1，有序2等），这些有序数列再次两两合并，最终直到成为一个完整的有序数列。

归并排序升序排序的代码

public void mergeSort(int[] array, int[] tmpArray, int left, int right){
    //递归实现归并排序
    if (left < right){
        int mid = (left + right)/2;
        mergeSort(array, tmpArray, left, mid);
        mergeSort(array, tmpArray, mid + 1, right);
        //将部分有序数列合并为一个更大的有序数列
        merge(array, tmpArray, left, mid, right);
    }
}

private void merge(int[] array, int[] tmpArray, int left, int mid,  int right){
    int lStart = left; int lEnd = mid; int rStart = mid + 1; int rEnd = right;
    int k = left;
    //合并两个有序子数组为一个完整的有序数组，结果存储在暂存数组中
    while(lStart <= lEnd && rStart <= rEnd){
        if (array[lStart] < array[rStart]){
            tmpArray[k] = array[lStart];
            lStart++;
        } else {
            tmpArray[k] = array[rStart];
            rStart++;
        }
        k++;
    }
    while (rStart <= rEnd){
        tmpArray[k++] = array[rStart++];
    }
    while (lStart <= lEnd){
        tmpArray[k++] = array[lStart++];
    }
    //从暂存数组拷贝有序数列到原来数组中
    for (int i = left; i <= right; ++i){
        array[i] = tmpArray[i];
    }
}