MergeSort原理及其实现

在排序算法的发展历史上，归并排序具有特殊的地位，它是第一个可以在最坏的情况下依然可以保持O(nlogn)运行时间的确定性排序算法。

与起泡排序通过反复调用单趟扫描交换类似，归并排序也可以理解为是通过反复调用所谓的二路归并算法实现的。所谓二路归并，就是将两个有序序列合并成一个有序序列。归并排序所需的时间业主要决定于各趟二路归并所需的时间总和。

二路归并属于迭代算法。每步迭代中，只需要比较两个待归并向量的首元素，将小者去除并追加到输出向量的末尾，该元素在原向量中的后继向量则成为新的首元素。如此往复，直到某一向量为空。最后，将另一个非空的向量整体接至输出向量末尾。

MergeSort原理及其实现 MergeSort原理及其实现

//
// Created by krislyy on 2018/11/14.
//

#ifndef ALGORITHM_MERGESORT_H
#define ALGORITHM_MERGESORT_H

namespace Algorithm {
    template <typename T>
    static void Merge(T *array, int lo, int mi, int hi) {
        //设置临时变量来存储新的有序数列
        T temp[hi - lo + 1];
        int pos = 0, lpos = lo, hpos = mi + 1;
        while (lpos <= mi && hpos <= hi) { //比较两组有序序列
            if (array[lpos] < array[hpos]) {
                temp[pos++] = array[lpos++];
            } else {
                temp[pos++] = array[hpos++];
            }
        } //比较两个数组中较小的元素放入新数组中
        while (lpos <= mi) { temp[pos++] = array[lpos++]; }
        while (hpos <= hi) { temp[pos++] = array[hpos++]; }
        //将临时数组放入原数组中
        for (int i = 0; i < pos; ++i) {
            array[i+lo] = temp[i];  //放入原数组lo~hi区间，此时这个区间有序
        }
    }

    template <typename T>
    static void MergeSort(T *array, int lo, int hi) {
        int mi = (hi + lo) / 2;   //以中点为边界
        if (lo < hi) {
            MergeSort(array, lo, mi);
            MergeSort(array, mi+1, hi);   //分别排序
            Merge(array, lo, mi, hi); //归并
        }
    }
}

#endif //ALGORITHM_MERGESORT_H