一、简介

归并排序使用了递归分治的思想，即先递归划分子问题，然后合并结果。
把待排序列看成由两个有序的子序列，然后合并两个子序列，然后把子序列看成由两个有序序列。倒着来看，其实就是先两两合并，然后四四合并，最终形成有序序列。

二、步骤

三、示例

四、代码实现

// 将arr[l...mid]和arr[mid+1...r]两部分进行归并
template<typename T>
void __mergeSort(T arr[], int l, int mid, int r) {
    T aux[r - l + 1];
    for (int i = l; i <= r; i++)
        aux[i - l] = arr[i];

    int i = l, j = mid + 1;
    for (int k = l; k <= r; k++) { // 判断索引的合法性
        if (i > mid) {
            arr[k] = aux[j - l];
        }
        else if (j > r) {
            arr[k] = aux[i - l];
            i++;
        }
        else if (aux[i - l] < aux[j - l]) {
            arr[k] = aux[i - l];
        }
        else {
            arr[k] = aux[j - l];
            j++;
        }
    }
}

// 递归使用递归排序，对arr[l...r]的范围进行排序
template<typename T>
void __mergeSort(T arr[], int l, int r) {
    //if（l >= r)
    //  return;
    int mid = (l + r) / 2;
    __mergeSort(arr, l, mid);
    __mergeSort(arr, mid + 1, r);
    __mergeSort(arr, l, mid, r);
}

template<typename T>
void mergeSort(T arr[], int n) {
    __mergeSort(arr, 0, n - 1);
}

五、评价

六、参考资料