C++ 归并排序 升序案例

归并排序是一种基于分治策略的高效排序算法。在升序案例中，它的工作原理是将待排序的数组不断划分为两个半部分，直到每个子数组只剩下一个元素，然后逐级合并这些有序的子数组，直至整个序列有序。

以下是归并排序的一个简单升序C++实现步骤：

1. **划分** (Divide): 首先，找到数组的中间位置，将数组分为两半。例如，如果数组长度为偶数，可以取中间两个元素的平均值作为分割点；如果奇数，则选择中间那个元素。

2. **递归排序** (Conquer): 对左右两个子数组分别递归地执行上述过程，直到子数组只有一个元素，这是最基础的情况，因为单个元素已经是有序的。

3. **合并** (Combine): 当子数组减少到只剩一个元素后，开始合并这两个已经排序好的子数组。创建一个新的临时数组，比较当前子数组的第一个元素和另一个子数组的第一个元素，选择较小的那个放入临时数组，并更新对应子数组的指针。这个过程会一直持续到所有的元素都被加入临时数组，完成一次合并。

4. **返回结果** (Combine and Return): 合并操作完成后，原来的数组就被更新为了有序状态。继续处理剩余的未排序部分，直到整个数组都排好序。

void merge(int arr[], int l, int m, int r) {
    int n1 = m - l + 1;
    int n2 = r - m;

    // 创建临时数组
    int L[n1], R[n2];

    // 将两个子数组复制到临时数组
    for (int i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for (int j = 0; j < n2; j++)
        R[j] = arr[m + 1+ j];

    // 合并临时数组回原数组
    int i = 0, j = 0, k = l;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    // 如果还有剩余元素，将其中一个数组剩下的元素添加到已排序部分
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

// 主函数，用于归并排序
void mergeSort(int arr[], int l, int r) {
    if (l < r) {
        int m = l+(r-l)/2; // 计算中间索引

        // 递归排序左半部分和右半部分
        mergeSort(arr, l, m);
        mergeSort(arr, m+1, r);

        // 合并两个有序部分
        merge(arr, l, m, r);
    }
}