#include <stdio.h>   // 导入打印积木的工具箱
#include <stdlib.h> // 导入其他小工具

// 合并两个有序小队（像拼小火车）
void merge(int arr[], int left, int mid, int right) {
    /* 参数说明：
       arr：积木大本营
       left：左边小队起点
       mid：左边小队终点（右边小队起点是mid+1）
       right：右边小队终点
    */
    
    // 1. 数清两队积木数量
    int n1 = mid - left + 1;  // 左边小队积木数量
    int n2 = right - mid;     // 右边小队积木数量
    
    // 2. 准备两个临时小推车存放积木
    int L[n1], R[n2];  // L小车放左边队，R小车放右边队

    // 3. 把左边积木搬到L小车（复制过程）
    for (int i = 0; i < n1; i++)
        L[i] = arr[left + i];  // 从左起点开始搬

    // 4. 把右边积木搬到R小车（复制过程）
    for (int j = 0; j < n2; j++)
        R[j] = arr[mid + 1 + j]; // 从中间点右边开始搬

    // 5. 开始拼装小火车（核心比较）
    int i = 0;      // L小车的指针（看哪块积木）
    int j = 0;      // R小车的指针
    int k = left;   // 大本营的起点位置
    
    // 比较两个小车最前面的积木，选小的放回大本营
    while (i < n1 && j < n2) {  // 当两队都还有积木时
        if (L[i] <= R[j]) {     // 左边小车积木更小
            arr[k] = L[i];       // 放左边积木到大本营
            i++;                 // 左边小车指针后移
        } else {                 // 右边小车积木更小
            arr[k] = R[j];       // 放右边积木到大本营
            j++;                 // 右边小车指针后移
        }
        k++;  // 大本营位置后移
    }

    // 6. 处理剩余的积木（当某队搬完了）
    while (i < n1) {   // 左边小车还有积木
        arr[k] = L[i]; // 全部搬到大本营
        i++;
        k++;
    }
    while (j < n2) {   // 右边小车还有积木
        arr[k] = R[j]; // 全部搬到大本营
        j++;
        k++;
    }
    // 现在两队积木合并成有序的小火车啦！
}

// 分积木大法（递归分治）
void mergeSort(int arr[], int left, int right) {
    /* 参数说明：
       arr：积木大本营
       left：当前区域的左边界
       right：当前区域的右边界
    */
    
    if (left < right) {  // 只要积木多于1块就继续分
        // 1. 找中间点（把积木堆分成两半）
        int mid = left + (right - left) / 2;  // 防止数字太大
        
        // 2. 魔法分解（左边分到底）
        mergeSort(arr, left, mid);      // 处理左边积木堆
        
        // 3. 魔法分解（右边分到底）
        mergeSort(arr, mid + 1, right); // 处理右边积木堆
        
        // 4. 拼装小火车（合并已排序的两队）
        merge(arr, left, mid, right);
    }
    // 如果只剩1块积木（left==right），直接返回（天然有序）
}

// 测试积木排序
int main() {
    // 准备8块乱序的积木
    int arr[] = {9, 5, 1, 4, 3, 2, 7, 6};
    int n = sizeof(arr) / sizeof(arr[0]);  // 计算积木总数

    // 展示原始积木
    printf("排序前: ");
    for (int i = 0; i < n; i++) printf("%d ", arr[i]);

    // 使用魔法分积木大法排序（从0号到7号积木）
    mergeSort(arr, 0, n - 1);

    // 展示排好队的积木
    printf("\n排序后: ");
    for (int i = 0; i < n; i++) printf("%d ", arr[i]);
    
    return 0; // 游戏结束
}

排序前: 9 5 1 4 3 2 7 6 排序后: 1 2 3 4 5 6 7 9 分积木步骤图解 假设积木 [9,5,1,4]：

第一刀：切成 [9,5] 和 [1,4]

再切左边：[9] 和 [5] → 合并成 [5,9]

再切右边：[1] 和 [4] → 合并成 [1,4]

最后合并：比较 [5,9] 和 [1,4] 的最前面：

1<5 → 放1

4<5 → 放4

放5 → 放9

结果：[1,4,5,9]

就像把混乱的积木不断对半拆分，最后把排好序的小块像拼火车一样连接起来！