归并排序

基本思想

      归并排序就是利用归并的思想实现的排序方法。其原理是假设初始序列含有n个记录，则可以看成是n个有序的子序列，每个子序列的长度为1，然后两两归并，得到n/2个长度为2或1的有序子序列，再两两归并······，如此重复，直到得到一个长度为n的有序序列为止。

合并部分的代码

    void merge(int[] array, int[] tmp, int start, int mid, int end) {
        int i = start;
        int j = mid;
        while (i < mid && j < end) {
            if (array[i] < array[j]) {
                tmp[start++] = array[i++];
            } else {
                tmp[start++] = array[j++];
            }
        }
        while (i < mid) {
            tmp[start++] = array[i++];
        }
        while (j < end) {
            tmp[start++] = array[j++];
        }
    }

非递归形式实现归并排序

    void mergeSort(int[] array) {
        int length = array.length;
        int[] tmp = new int[length];
        // i表示每个小子序列的步长
        int i = 1;
        while (i < length) {
            mergePass(array, tmp, i);
            i = i * 2;
            mergePass(tmp, array, i);
            i = i * 2;
        }
    }

    void mergePass(int[] array, int[] tmp, int index) {
        int length = array.length;
        int i;
        for (i = 0; i <= length - 2 * index; i = i + 2 * index) {
            merge(array, tmp, i, i + index, i + 2 * index);
        }
        if (i < length - index) {
            merge(array, tmp, i, i + index, length);
        } else {
            while (i < length) {
                tmp[i] = array[i++];
            }
        }
    }

递归形式实现归并排序

// TODO

归并排序的时间复杂度

      时间复杂度是O(nlogn)；归并排序是一种比较占用内存，但却效率高且稳定的算法。