算法思路

歸并排序是一種分治算法：首先將數(shù)組分成兩半，然后對(duì)每一半進(jìn)行歸并排序，最后將兩個(gè)有序的子數(shù)組合并，以得到最終的排序數(shù)組。為了簡(jiǎn)潔下面代碼中會(huì)調(diào)用 STL 的 $inplace\_merge$ 方法，這個(gè)方法的作用正是將兩個(gè)連續(xù)的有序區(qū)間合并為一個(gè)有序區(qū)間，當(dāng)然也可以自己按合并有序鏈表的思路寫一個(gè) $merge$ 方法~

a. 遞歸

自頂向下的遞歸排序

void merge_sort(vector<int> &li, int s, int e) {//li[s,e)為待排序的子數(shù)組
    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);//合并有序區(qū)間[s,mid)和[mid,e)
}

b. 棧模擬遞歸

用一個(gè)棧模擬遞歸排序中區(qū)間處理的過程，注意一個(gè)區(qū)間可能會(huì)在棧中出現(xiàn)兩次：第一次其兩個(gè)子區(qū)間還未排序，第二次其兩個(gè)子區(qū)間已經(jīng)有序，所以需要有一個(gè)額外的標(biāo)志位來區(qū)分一個(gè)區(qū)間在棧中的這兩種狀態(tài)。

void merge_sort_stack(vector<int> &li, int s, int e) {//li[s,e)為待排序的子數(shù)組
    stack<tuple<int, int, int>> st;
    st.emplace(s, e, 0);
    while (!st.empty()) {
        auto [l, r, tag] = st.top();//當(dāng)前區(qū)間為[l,r) , 標(biāo)志位為tag
        st.pop();
        if (tag == 0) {//當(dāng)前區(qū)間第一次出現(xiàn)
            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 {//當(dāng)前區(qū)間第二次出現(xiàn)
            int mid = (l + r) / 2;
            inplace_merge(li.begin() + l, li.begin() + mid, li.begin() + r);//合并有序區(qū)間[l,mid)和[mid,r)
        }
    }
}

c. 遞推

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

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