C++归并排序算法附示意图

下面是C++实现归并算法的代码，每个关键部分都有详细注释：

#include <iostream>
using namespace std;

// 将数组 arr 中 [l...mid] 和 [mid+1...r] 两部分进行归并
void merge(int arr[], int l, int mid, int r) {
    // 定义需要用到的临时变量
    int i = l;          // i 表示左半部分数组的起始位置
    int j = mid + 1;    // j 表示右半部分数组的起始位置
    int k = 0;          // k 表示当前排序到的位置
    int tmp[r - l + 1]; // 临时数组，用于存储排序后的结果

    // 将左半部分和右半部分数组中的元素逐一比较，较小者存入临时数组中
    while (i <= mid && j <= r) {
        if (arr[i] < arr[j]) {
            tmp[k++] = arr[i++];
        } else {
            tmp[k++] = arr[j++];
        }
    }

    // 将剩余的元素依次存入临时数组中
    while (i <= mid) {
        tmp[k++] = arr[i++];
    }
    while (j <= r) {
        tmp[k++] = arr[j++];
    }

    // 将临时数组中的元素复制回原数组中
    for (i = l, k = 0; i <= r; i++, k++) {
        arr[i] = tmp[k];
    }
}

// 归并排序
void mergeSort(int arr[], int l, int r) {
    if (l >= r) {
        return;
    }

    int mid = (l + r) / 2;  // 中间位置

    // 递归地对左半部分和右半部分数组进行排序
    mergeSort(arr, l, mid);
    mergeSort(arr, mid + 1, r);

    // 将左半部分和右半部分数组进行归并
    merge(arr, l, mid, r);
}

int main() {
    int arr[] = {5, 4, 3, 2, 1};
    int len = sizeof(arr) / sizeof(int);

    mergeSort(arr, 0, len - 1);

    for (int i = 0; i < len; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;

    return 0;
}

归并排序的核心在于归并函数merge()的实现，其实现过程如下：

1. 定义需要用到的临时变量，包括数组左半部分起始位置i、右半部分起始位置j、排序到的位置k以及临时数组tmp。

2. 将左半部分和右半部分数组中的元素逐一比较，较小者存入临时数组中。

3. 将剩余的元素依次存入临时数组中。

4. 将临时数组中的元素复制回原数组中，完成排序。

1. 归并排序函数mergeSort()的实现过程如下：

2. 判断是否需要进行排序，如果当前数组的起始位置l大于等于结束位置r，则无需排序。

3. 计算中间位置mid，将数组分成左半部分和右半部分。

4. 递归地对左半部分和右半部分数组进行排序，直到无法继续划分。

5. 将左半部分和右半部分数组进行归并。

在main()函数中，我们创建了一个测试数组arr，并调用mergeSort()函数进行排序，最后输出排序后的结果。

归并排序的时间复杂度为 O(nlogn)，是一种稳定的排序算法，常用于对大规模数组进行排序。

下面是一个例子，用文本格式画出归并排序的递归和回溯的过程：

原始数组：{5, 4, 3, 2, 1}

mergeSort(arr, 0, 4)
    mergeSort(arr, 0, 2)
        mergeSort(arr, 0, 1)
            mergeSort(arr, 0, 0)
            mergeSort(arr, 1, 1)
            merge(arr, 0, 0, 1) -> {4, 5, 3, 2, 1}
        mergeSort(arr, 2, 2)
        merge(arr, 0, 1, 2) -> {3, 4, 5, 2, 1}
    mergeSort(arr, 3, 4)
        mergeSort(arr, 3, 3)
        mergeSort(arr, 4, 4)
        merge(arr, 3, 3, 4) -> {3, 4, 5, 1, 2}
    merge(arr, 0, 2, 4) -> {1, 2, 3, 4, 5}

上面的示例中，我们以数组 {5, 4, 3, 2, 1} 为例，展示了归并排序的递归和回溯过程。

在归并排序的递归过程中，我们将数组逐步划分为更小的子数组，并对这些子数组进行排序。具体步骤如下：

1. 首先调用 mergeSort(arr, 0, 4) 对整个数组进行排序。

2. mergeSort(arr, 0, 4) 中间位置为 mid = (0 + 4) / 2 = 2，将数组分为 {5, 4, 3} 和 {2, 1} 两部分。

3. 对左半部分数组 {5, 4, 3} 调用 mergeSort(arr, 0, 2) 进行排序。

4. mergeSort(arr, 0, 2) 中间位置为 mid = (0 + 2) / 2 = 1，将数组分为 {5, 4} 和 {3} 两部分。

5. 对左半部分数组 {5, 4} 调用 mergeSort(arr, 0, 1) 进行排序。

6. mergeSort(arr, 0, 1) 中间位置为 mid = (0 + 1) / 2 = 0，将数组分为 {5} 和 {4} 两部分。

7. 对左半部分数组 {5} 调用 mergeSort(arr, 0, 0) 进行排序，无需排序。

8. 对右半部分数组 {4} 调用 mergeSort(arr, 1, 1) 进行排序，无需排序。

9. 对两部分数组 {5} 和 {4} 进行归并，得到 {4, 5}。

10. 对右半部分数组 {3} 调用 mergeSort(arr, 2, 2) 进行排序，无需排序。

11. 对左半部分数组 {4, 5} 和右半部分数组 {3} 进行归并，得到 {3, 4, 5}。

12. 对左半部分数组 {3, 4, 5} 和右半部分数组 {2, 1} 进行归并，得到 {1, 2, 3, 4, 5}。

在归并排序的回溯过程中，我们将已经排序好的子数组进行归并。具体步骤如下：

1. 当调用 mergeSort(arr, 0, 0) 和 mergeSort(arr, 3, 3) 时，由于数组只有一个元素，无需排序。

2. 当调用 merge(arr, 0, 0, 1) 时，左半部分数组 {4} 和右半部分数组 {5} 进行归并，得到 {4, 5}。

3. 当调用 merge(arr, 3, 3, 4) 时，左半部分数组 {1} 和右半部分数组 {2} 进行归并，得到 {1, 2}。

4. 当调用 merge(arr, 0, 1, 2) 时，左半部分数组 {4, 5} 和右半部分数组 {3} 进行归并，得到 {3, 4, 5}。

5. 最后一次调用 merge(arr, 0, 2, 4)，将整个数组进行归并，得到 {1, 2, 3, 4, 5}。