归并排序

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法的一个非常典型的应用。

分治法将问题分（divide）成一些小问题然后递归求解，而治（conquer）的阶段则将分的阶段得到的各答案“修补”在一起，即分而治之。

算法步骤

1. 自上而下递归拆分子序列，直指子序列只有一个元素；
2. 自下而上合并子序列为一个有序序列；

动图演示

代码实现

template <typename T>
T min(T x, T y) {
    return x < y ? x : y;
}
template <typename T>
void mergeSort(T arr[], size_t len) {
    T *a = arr;
    T *b = new T[len];
    for (int setp = 1; setp < len; setp += setp) {
        // 外层循环是分的层级；自下而上的遍历
        for (int start = 0; start < len; start = start + setp * 2) {
            // 内层循环是归并的步骤，自左向右的遍历；
            int left = start;
            int mid = min(start + setp, (int)len);
            int right = min(start + setp * 2, (int)len);
            
            int k = left;
            int s1 = left, e1 = mid;
            int s2 = mid, e2 = right;
            
            while (s1 < e1 && s2 < e2) {
                b[k++] = a[s1] < a[s2] ? a[s1++] : a[s2++];
            }
            while (s1 < e1) {
                b[k++] = a[s1++];
            }
            while (s2 < e2) {
                b[k++] = a[s2++];
            }
        }
        T *temp = a;
        a = b;
        b = temp;
    }
    
    if (arr != a) {
        for (int i = 0; i < (int)len; i++) {
            b[i] = a[i];
        }
        b = a;
    }
    delete[] b;
}

int main(int argc, const char * argv[]) {
    int arr[] = {9,8,7,6,5,4,3,2,1};
    mergeSort(arr, sizeof(arr) / sizeof(int));
    return 0;
}