11.12 合併排序法（延伸知識）

#include <iostream>
using namespace std;

int main() {
    int a[4] = {1, 3, 5, 9};       // 已排序
    int b[3] = {2, 3, 8};          // 已排序
    int c[7];                      // 合併結果

    int i = 0, j = 0, k = 0;       // i 看 a、j 看 b、k 寫 c
    while (i < 4 && j < 3) {
        if (a[i] <= b[j]) {        // 兩隊排頭比一比，小的先走
            c[k] = a[i];
            i++;
        } else {
            c[k] = b[j];
            j++;
        }
        k++;
    }
    while (i < 4) { c[k] = a[i]; i++; k++; }   // a 還有剩：全部搬過去
    while (j < 3) { c[k] = b[j]; j++; k++; }   // b 還有剩：全部搬過去

    for (int t = 0; t < 7; t++) {
        cout << c[t] << ' ';
    }
    cout << '\n';
    return 0;
}

#include <iostream>
#include <algorithm>   // min 住在這（上冊 7.6）
using namespace std;

const int MAX_N = 200000;
int a[MAX_N], b[MAX_N];   // a：目前的資料；b：這一輪合併出來的結果

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    // seg＝目前每段的長度：1、2、4、8……直到蓋過整個數列
    for (int seg = 1; seg < n; seg += seg) {
        // 每次處理相鄰的兩段，start 是左段的開頭
        for (int start = 0; start < n; start += seg + seg) {
            int low = start;                        // 左段開頭
            int mid = min(start + seg, n);          // 左段結尾＝右段開頭
            int high = min(start + seg + seg, n);   // 右段結尾
            int k = low;                            // 結果要寫進 b 的第幾格

            int start1 = low, end1 = mid;     // 左段還沒搬走的範圍
            int start2 = mid, end2 = high;    // 右段還沒搬走的範圍
            while (start1 < end1 && start2 < end2) {
                if (a[start1] <= a[start2]) {      // 兩段的排頭比一比，小的先走
                    b[k++] = a[start1++];
                } else {
                    b[k++] = a[start2++];
                }
            }
            while (start1 < end1) b[k++] = a[start1++];   // 左段還有剩：全部搬過去
            while (start2 < end2) b[k++] = a[start2++];   // 右段還有剩：全部搬過去
        }

        for (int i = 0; i < n; i++) {   // 這一輪的成果搬回 a，下一輪繼續用
            a[i] = b[i];
        }
    }

    for (int i = 0; i < n; i++) {
        cout << a[i] << ' ';
    }
    cout << '\n';
    return 0;
}