c++实现归并排序对数组排序

在C++中实现归并排序对数组排序，你可以编写一个函数，采用递归的方式来进行。以下是一个简单的示例：

#include <iostream>
using namespace std;

// 合并两个已经排好序的子数组
void merge(int arr[], int l, int m, int r) {
    int n1 = m - l + 1;
    int n2 = r - m;
    int L[n1], R[n2];

    // 将左子数组复制到L[]数组
    for (int i=0; i<n1; i++)
        L[i] = arr[l + i];
    // 将右子数组复制到R[]数组
    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);
    }
}

int main() {
    int arr[] = {12, 11, 13, 5, 6, 7};
    int arr_size = sizeof(arr) / sizeof(arr[0]);

    cout << "Original array: ";
    for (int i=0; i<arr_size; i++)
        cout << arr[i] << " ";

    mergeSort(arr, 0, arr_size - 1);

    cout << "\nSorted array: ";
    for (int i=0; i<arr_size; i++)
        cout << arr[i] << " ";

    return 0;
}

在这个例子中，`mergeSort()`函数是主函数，它调用了自身两次进行递归划分，然后`merge()`函数负责合并两个有序部分。当你运行这个程序时，它会输出原始数组和排序后的数组。