如何在C++中实现基于分治策略的归并排序算法？

在C++中，归并排序是一种采用分治策略的经典算法。它将待排序数组分成两个大小相等的部分，分别对这两部分进行递归排序，然后合并已排序的部分。以下是基本步骤：

1. **分割（Divide）**：首先，将输入数组`arr`一分为二，通常取数组长度的一半作为分界点。

void mergeSort(int arr[], int left, int right) {
    if (left < right) {
        // ...
    }
}

2. **递归（Conquer）**：对左右两部分递归地调用`mergeSort()`函数。

void mergeSort(int arr[], int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
    }
}

3. **合并（Combine）**：当两个部分都被排序后，将它们合并成一个有序数组。这一步创建了一个临时数组`temp`，并将左、右部分按顺序复制到`temp`，同时保持左侧元素小于右侧元素的条件。

void merge(int arr[], int temp[], int left, int mid, int right) {
    int i = left, j = mid + 1, k = 0;

    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
        }
    }

    // 将剩余未比较的元素添加到结果数组
    while (i <= mid) {
        temp[k++] = arr[i++];
    }

    while (j <= right) {
        temp[k++] = arr[j++];
    }

    // 将结果复制回原始数组
    for (int x = 0; x < k; ++x) {
        arr[left + x] = temp[x];
    }
}

// 调用合并操作
void mergeSort(int arr[], int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, arr, left, mid, right);
    }
}