這章節要介紹讓我腦洞大開的一個sort方法，merge sort。

Merge Sort在CS61B很前面介紹Asymptotics的章節就會提到，然後後面的章節會再提到一遍，不過我比較喜歡前面Asymptotics的介紹方法，所以會引用這段推導來說明Merge Sort。

我們知道Selection Sort的runtime會是$O(N^2)$，假設我們定義一個時間單位叫做AU(arbitrary units of time)，而以下N長度的list透過selection sort所要花費的時間大約為$N^2$：

而假設我們有兩個sort好的list，把他們merge成一個sorted list所要花費的runtime會是Θ(N)：

精彩的來了！如果原本要花費大約4096AU的N=64 list，如果把它拆成兩個N=32的list，各自做完selection sort後再merge，總共runtime會是多少呢：

各自N=32會花費1024AU * 2，再加上最後merge的64AU，總共是2112AU！

老天鵝，我們只是換一個做法，runtime就直接減少快一半了！而且你說這是什麼很難很複雜的操作嗎？也沒有！

這樣就很屌了，但還有更猛的。我們只是把原本的list分兩半就獲得很顯著的效果了，讓我們更貪心一點，不要只分成2份，2份再繼續分成4份：

4份繼續分成8份！8份繼續分…….直到分成64份！每一份就只有一個元素！最終會是384AU：

我們來用代數看看，若是分到只有一個元素後，不斷每層每層merge上來，最終runtime會是Θ(N log N)！

真的很猛。

Slides are from Josh Hug CS61B

This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License