#include <stdio.h> 
// 归并函数
void merge(int arr[], int left, int middle, 
                    int right, int temp[]) {
    int i = left;  // 左数组起始索引
    int j = middle + 1; // 右数组起始索引
    int k = left; // 合并后数组起始索引 
    // 将数据复制到临时数组
    for (int m = left; m <= right; ++m)  
        temp[m] = arr[m]; 
    // 合并临时数组到 arr[left..right]
    while (i <= middle && j <= right) {
        if (temp[i] <= temp[j]) 
            arr[k++] = temp[i++];
          else 
            arr[k++] = temp[j++]; 
    } 
    // 拷贝剩余元素（如果有）
    while (i <= middle)  
        arr[k++] = temp[i++]; 
} 
// 归并排序函数
void mergeSort(int arr[], int left, int right, int temp[]) {
    if (left < right) {
        int middle = left + (right - left) / 2;
        mergeSort(arr, left, middle, temp); // 排左半部分
        mergeSort(arr, middle + 1, right, temp); // 排右半部分
        merge(arr, left, middle, right, temp); // 合并两个已排部分
    }
} 
// 打印数组
void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++) 
        printf("%d ", arr[i]); 
    printf("\n");
}

int main() {
    int arr[] = {8, 7, 6, 15, 4, 3, 2, 10};
    int arrSize = sizeof(arr) / sizeof(arr[0]); 
    int temp[arrSize]; 
    printf("原始数组: ");
    printArray(arr, arrSize); 
    mergeSort(arr, 0, arrSize - 1, temp); 
    printf("排序后的数组: ");
    printArray(arr, arrSize); 
    return 0;
}