编写c/c++程序,实现二路合并排序(merge sort)

二路合并排序是一种经典的排序算法，通过分治的思想将一个序列不断地二分，直到每个子序列只有一个元素，然后通过归并操作将子序列两两合并。以下是用C/C++编写的二路合并排序程序的简单示例：

#include <stdio.h>

// 归并操作
void merge(int arr[], int left[], int left_size, int right[], int right_size) {
    int i = 0, j = 0, k = 0;
    
    // 合并两个子序列
    while (i < left_size && j < right_size) {
        if (left[i] <= right[j]) {
            arr[k++] = left[i++];
        } else {
            arr[k++] = right[j++];
        }
    }
    
    // 将剩余元素拷贝到arr中
    while (i < left_size) {
        arr[k++] = left[i++];
    }
    while (j < right_size) {
        arr[k++] = right[j++];
    }
}

// 二路合并排序
void mergeSort(int arr[], int size) {
    if (size <= 1) {
        return;
    }
    
    int mid = size / 2;
    int left[mid], right[size - mid];
    
    // 将原数组分成两个子序列
    for (int i = 0; i < mid; i++) {
        left[i] = arr[i];
    }
    for (int i = mid; i < size; i++) {
        right[i - mid] = arr[i];
    }
    
    // 递归地对子序列进行排序
    mergeSort(left, mid);
    mergeSort(right, size - mid);
    
    // 归并合并两个子序列
    merge(arr, left, mid, right, size - mid);
}

int main() {
    int arr[] = {9, 2, 7, 5, 4, 3, 8, 1, 6};
    int size = sizeof(arr) / sizeof(arr[0]);
    
    printf("原数组：");
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    
    mergeSort(arr, size);
    
    printf("\n排序后：");
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    
    return 0;
}

在上述程序中，首先定义了一个`merge`函数用于合并两个子序列，然后定义了`mergeSort`函数用于递归地进行二路合并排序。在主函数中，我们定义了一个待排序的数组，并对其进行了打印和排序操作，最后打印出排序后的数组。

这个程序使用了递归的方式实现了二路合并排序算法，通过将数组不断地二分，然后再合并有序的子序列，从而得到完整的有序序列。