【舌尖上的演算法】Day15 -- Divide and Conquer - Merge Sort

2020 IT邦鐵人賽

Posted by Hank Lee on Tuesday, September 22, 2020

2 Minutes Read

Table of Contents

本系列文章同步分享於IT邦幫忙第12屆鐵人賽

前言

一連五天,我們介紹了Decrease and Conquer,今天和明天我們要介紹另一個主題 – Divide and Conquer和兩種屬於這個類別的演算法,分別是Merge Sort(今天)和Quick Sort(明天),那就讓我們開始今天的主題吧。


Divide and Conquer的運作方式

Divide and Conquer

Decrease and ConquerDivide and Conquer都是將大問題拆解成小問題解決的運作方式,然而前者是將小問題的解決方式衍生到大問題去解決,但後者則是將解決小問題而有的小結果合併起來,變成大問題的解答,所以兩者還是有其區別。從上示意圖可知,原先有一問題(紅色),其大小為n,將其拆解成兩個子問題(藍色),大小分別為n/2,再進一步拆解成四個小子問題(大小分別為n/4)(黃色),此時,再針對這四個小子問題去解決,進而取得小子問題的解答(結果)(綠色),再將四個小子結果合併成兩個子結果(粉色),最後將兩個子結果合併成最終的結果(黑色);這個就是Divide and Conquer的運作流程。


Merge Sort的流程

Merge Sort其實就是標準的Divide and Conquer,完全按照上面的圖進行拆解和組合,我們來看看GIF了解實際上Merge Sort是如何進行的吧:

Merge Sort

從上GIF圖可以看到,在進行Divide的時候,會拆解成最小單位,然後在每一步Conquer的過程中進行Sort的動作,如此一來在進入下一階段的Conquer前,就會是兩個已經排列過的陣列合併。


Merge Sort的時間複雜度

Merge Sort保留了Binary Search的『砍半』手法,所以只要有砍半的動作,時間複雜度就會是𝜪(㏒2 n)但是,Merge Sort在進行Merge的時候,最壞的情況(Worst Case)是每一步的Conquer都要去做兩個陣列完整的比較後才能完成排序與合併,而這個動作的時間複雜度為𝜪(n);因此,整體來說,Merge Sort的時間複雜度需要合併這兩個結果,即為𝜪(n·㏒2 n)


小結

  1. Divide and Conquer是將大問題拆解成小問題解決後,再將所有小問題的結果合併成大問題的結果。
  2. Merge Sort的時間複雜度為𝜪(n·㏒2 n)

預告

明天我們將會介紹另一個Divide and Conquer的演算法-Quick Sort。


References

  1. Introduction to the Design and Analysis of Algorithms, 3rd Edition, by Anany Levitin