C++說要有順序，于是便誕生了眾多的排序算法。

眾多排序算法中有一個(gè)玄學(xué)算法——?dú)w并排序。

歸并排序有兩個(gè)步驟——先分而治之。歸并算法的核心是分治，顧名思義，分，就是把問題簡化，分割成一個(gè)個(gè)容易計(jì)算的小問題；治，則是把求得子問題的所有答案匯總成整個(gè)問題的最終答案（為毛讓我想起了動(dòng)歸？）。

首先，我們需要通過遞歸和二分的方法，將需要排序的原數(shù)組分割成多個(gè)臨時(shí)數(shù)組。每個(gè)臨時(shí)數(shù)組都是（在該次遞歸中的）原數(shù)組的一半長度，直至分割成無法再次分割的最小單位（在歸并排序中就是數(shù)組中只有一個(gè)數(shù)，n=1），?這部分的時(shí)間復(fù)雜度是log2n；

接著是“并”，也通過遞歸來實(shí)現(xiàn)，將每兩個(gè)已有序的臨時(shí)數(shù)組 合并成一個(gè)有序的臨時(shí)數(shù)組（對(duì)于每個(gè)臨時(shí)數(shù)組的區(qū)間來說都是有序的），將這部分有序的數(shù)還原到原數(shù)組中，最終將所有子數(shù)組合并成有序的原數(shù)組，這部分的時(shí)間復(fù)雜度是n（每個(gè)數(shù)掃一遍）。

最終的時(shí)間復(fù)雜度就是n*log2n。

詳細(xì)的見代碼描述。

有疑問評(píng)論區(qū)歡迎留言。

練習(xí)完的可以去洛谷P1177快速排序 提交（https://www.luogu.com.cn/problem/P1177），所有的排序題目都可以在上面提交。

如果覺得太簡單的可以嘗試洛谷P1908逆序?qū)Γ╤ttps://www.luogu.com.cn/problem/P1908），雖然不是排序，但需要用到歸并排序的思想（分治yyds）。

最后，老師的任務(wù)已經(jīng)完成了，祝愿我原神胡桃二十抽直接出金！

QwQ Orz QaQ