归并排序及其优化

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。归并排序是一种稳定的排序方法。

1. 原理  

归并排序的原理上面已经说了，即先使每个子序列有序，然后再将子序列变为有序，最终就完成了整个排序。

而子序的划分 则是简单暴力的   从中间一刀切  也就是  (start+end) / 2 的位置将序列变为两个序列，然后进行归并，依次递归。最终得到有序序列。

第一步：申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列

第二步：设定两个指针，最初位置分别为两个已经排序序列的起始位置

第三步：比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置

重复步骤3直到某一指针超出序列尾

将另一序列剩下的所有元素直接复制到合并序列尾

如图：

直接上初始版本C++代码：

/**
 * 归并 两个有序的数组
 * @tparam T
 * @param arr
 * @param start
 * @param mid
 * @param end
 */
template<typename T>
void __merge(T arr[], int start, int mid, int end) {
    // 首先开辟一个新空间，用来进行归并
    T aux[end - start + 1];

    for (int i = start; i <= end; ++i) {
        aux[i - start] = arr[i];
    }

    // std::cout << "merge" << std::endl;
    // printArray(aux, end - start + 1);

    int i = start, j = mid + 1;

    for (int k = start; k <= end; k++) {
        if (i > mid) {
            arr[k] = aux[j - start];
            j++;
        } else if (j > end) {
            arr[k] = aux[i - start];
            i++;
        } else if (aux[i - start] < aux[j - start]) {
            arr[k] = aux[i - start];
            i++;
        } else {
            arr[k] = aux[j - start];
            j++;
        }
    }

}

/**
 * 归并排序子过程
 * @tparam T
 * @param start
 * @param end
 * @param arr
 */
template<typename T>
void __mergeSort(int start, int end, T arr[]) {
    if (start >= end) {
        return;
    }

    // 当start和end 特别大的时候，会发生溢出的问题
    int mid = (start + end) / 2;

    __mergeSort(start, mid, arr);
    __mergeSort(mid + 1, end, arr);
    __merge(arr, start, mid, end);

}

/**
 * 归并排序
 * @tparam T
 * @param arr
 * @param n
 */
template<typename T>
void mergeSort(T arr[], int n) {

    __mergeSort(0, n - 1, arr);

}

第一次优化：

但是这样的话，不管什么情况都会进行归并，即使序列本来就已经是有序了。

比如：

1 2 4 - 5 7 9

已经有序了，所以我们是可以不进行归并操作的，否则即会占用大量内存，也会消耗时间，十分损耗性能，此时我们只需要进行判断则可确定是否要进行归并

这个判断的临界值应该是  arr[mid] 和 arr[mid + 1] ， 如果arr[mid] > arr[mid + 1]说明序列此时不是有序的，则进行归并，否则跳过。 对此我们只需要修改  __mergeSort函数即可：

template<typename T>
void __mergeSort(int start, int end, T arr[]) {
    if (start >= end) {
        return;
    }

    // 当start和end 特别大的时候，会发生溢出的问题
    int mid = (start + end) / 2;

    __mergeSort(start, mid, arr);
    __mergeSort(mid + 1, end, arr);
    // __merge(arr, start, mid, end);
    if (arr[mid] > arr[mid + 1]) {
        __merge(arr, start, mid, end);
    }

}

第二次优化：

通过插入排序进行进一步优化，当排序进行到最后的一定步数时，可以直接通过插入排序进行排序其子序列，可以取得比归并更快的速度，这里取15尝试：

首先定义一个专为优化其他排序算法的插入排序函数

template<typename T>
void insertionSort(T arr[], int l, int r) {
    // 首先从第二个元素开始，因为第一个元素本来就是已经确定了的没有可比较元素
    for (int i = l + 1; i <= r; i++) {

        T data = arr[i];
        int j = i - 1;
        for (; j >= 0 && data < arr[j]; j--) {
            // 跟前一个元素比较，如果比他小则切换目标的位置
            arr[j + 1] = arr[j];
        }

        arr[j + 1] = data;

    }
}

然后再修改__mergeSort函数：

template<typename T>
void __mergeSort(int start, int end, T arr[]) {
    // if (start >= end) {
    //     return;
    // }

    if (end - start <= 15) {
        insertionSort(arr, start, end);
        return;
    }

    // 当start和end 特别大的时候，会发生溢出的问题
    int mid = (start + end) / 2;

    __mergeSort(start, mid, arr);
    __mergeSort(mid + 1, end, arr);
    // __merge(arr, start, mid, end);
    if (arr[mid] > arr[mid + 1]) {
        __merge(arr, start, mid, end);
    }

}