C++归并排序原理思路

归并排序是一种基于分治法的排序算法，它的基本思路是将待排序的序列不断地划分成更小的子序列，直到每个子序列只有一个元素，然后再将这些子序列两两合并，直到最终得到一个有序的序列。

具体的归并排序算法步骤如下：
1. 将待排序序列不断地二分划分，直到每个子序列只有一个元素。
2. 将相邻的两个子序列进行合并，合并时比较两个子序列的元素大小，将较小的元素放在新的序列中。
3. 重复步骤2，直到所有的子序列都合并成一个有序的序列。

归并排序的关键在于合并操作，合并操作的实现可以使用一个辅助数组来存储合并后的结果。具体的合并操作步骤如下：
1. 创建一个与待排序序列大小相同的辅助数组。
2. 将待排序序列的两个子序列分别赋值给辅助数组的两个子序列。
3. 使用两个指针分别指向辅助数组的两个子序列的起始位置，比较两个指针所指向的元素大小，将较小的元素放入原始序列中，并将指针向后移动一位。
4. 重复步骤3，直到其中一个子序列的元素全部放入原始序列中。
5. 将另一个子序列中剩余的元素依次放入原始序列中。

下面是C++实现归并排序的代码示例：

#include <iostream>
using namespace std;

// 合并两个有序子序列
void merge(int arr[], int left, int mid, int right) {
    int i = left; // 左子序列的起始位置
    int j = mid + 1; // 右子序列的起始位置
    int k = 0; // 辅助数组的起始位置
    int* temp = new int[right - left + 1]; // 辅助数组

    // 比较两个子序列的元素大小，将较小的元素放入辅助数组中
    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 m = 0; m < k; m++) {
        arr[left + m] = temp[m];
    }

    delete[] temp;
}

// 归并排序
void mergeSort(int arr[], int left, int right) {
    if (left < right) {
        int mid = (left + right) / 2;
        mergeSort(arr, left, mid); // 对左子序列进行归并排序
        mergeSort(arr, mid + 1, right); // 对右子序列进行归并排序
        merge(arr, left, mid, right); // 合并两个有序子序列
    }
}

int main() {
    int arr[] = {5, 2, 8, 3, 1, 6};
    int n = sizeof(arr) / sizeof(arr[0]);

    mergeSort(arr, 0, n - 1);

    cout << "Sorted array: ";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;

    return 0;
}