算法思路

歸并排序是一種分治算法：首先將數組分成兩半，然后對每一半進行歸并排序，最后將兩個有序的子數組合并，以得到最終的排序數組。為了簡潔下面代碼中會調用 STL 的 $inplace\_merge$ 方法，這個方法的作用正是將兩個連續的有序區間合并為一個有序區間，當然也可以自己按合并有序鏈表的思路寫一個 $merge$ 方法~

a. 遞歸

自頂向下的遞歸排序

void merge_sort(vector<int> &li, int s, int e) {//li[s,e)為待排序的子數組
    if (e - s <= 1)
        return;
    int mid = (s + e) / 2;
    merge_sort(li, s, mid);
    merge_sort(li, mid, e);
    inplace_merge(li.begin() + s, li.begin() + mid, li.begin() + e);//合并有序區間[s,mid)和[mid,e)
}

b. 棧模擬遞歸

用一個棧模擬遞歸排序中區間處理的過程，注意一個區間可能會在棧中出現兩次：第一次其兩個子區間還未排序，第二次其兩個子區間已經有序，所以需要有一個額外的標志位來區分一個區間在棧中的這兩種狀態。

void merge_sort_stack(vector<int> &li, int s, int e) {//li[s,e)為待排序的子數組
    stack<tuple<int, int, int>> st;
    st.emplace(s, e, 0);
    while (!st.empty()) {
        auto [l, r, tag] = st.top();//當前區間為[l,r) , 標志位為tag
        st.pop();
        if (tag == 0) {//當前區間第一次出現
            if (r - l <= 1)
                continue;
            int mid = (l + r) / 2;
            st.emplace(l, r, 1);
            st.emplace(l, mid, 0);
            st.emplace(mid, r, 0);
        } else {//當前區間第二次出現
            int mid = (l + r) / 2;
            inplace_merge(li.begin() + l, li.begin() + mid, li.begin() + r);//合并有序區間[l,mid)和[mid,r)
        }
    }
}

c. 遞推

自底向上的遞推：首先兩兩一組的合并長為 $2^0$ 的子數組，再兩兩一組的合并長為 $2^1$ 的子數組，$?$ ，直到 $2^k$ 不小于數組長度時遞推結束。注意每一輪合并中最后一組的右邊的子數組的長度可能小于 $2^k$。

void merge_sort(vector<int> &li, int s, int e) {//li[s,e)為待排序的子數組
    int n = e - s;
    for (int len = 1; len < n; len *= 2)//合并的子數組的長度len不超過n
        for (int i = s; i + len < e; i += len * 2)//逐對枚舉兩個相鄰的子數組
            inplace_merge(li.begin() + i, li.begin() + i + len, li.begin() + min(e, i + len * 2));//合并有序區間[i,i+len)和[i+len,min(e,i+len*2))
}