C++ 原地归并排序

C++ 原地归并排序是一种基于分治思想的排序算法。它的主要思路是将待排序的数组分成两个部分，对这两个部分进行排序，然后将这两个部分合并起来，最终得到有序的数组。

在原地归并排序中，我们需要先将数组分成两部分，然后对这两部分进行排序。排序完成后，我们需要将这两个有序的部分合并成一个有序的数组。在合并的过程中，我们需要利用到额外的空间来存储两个部分合并后的结果。

如果不使用额外的空间，则需要对数组进行原地归并。具体实现可以使用类似于归并排序中合并两个有序数组的方式，从前往后依次比较两个部分中的元素，将较小的元素放入原数组的前面。当其中一个部分已经全部放入原数组后，另一个部分中剩余的元素直接放入原数组的末尾即可。

下面是 C++ 原地归并排序的实现代码：

void merge(int arr[], int l, int m, int r) {
    int i = l, j = m+1, k = l;
    while (i <= m && j <= r) {
        if (arr[i] <= arr[j]) {
            i++;
        } else {
            int tmp = arr[j];
            for (int p = j-1; p >= i; p--) {
                arr[p+1] = arr[p];
            }
            arr[i] = tmp;
            i++; m++; j++;
        }
    }
}

void mergeSort(int arr[], int l, int r) {
    if (l >= r) return;
    int m = l + (r-l)/2;
    mergeSort(arr, l, m);
    mergeSort(arr, m+1, r);
    merge(arr, l, m, r);
}