合併排序法介紹

合併排序法是什麼

透過分治法的策略將一組未排序的數列做由小至大排序。其步驟為

1. 分割（divide）

將數列遞迴分割為一半，直到子數列元素為一個才停止分割。

2.合併（conquer）

將子數列兩兩合併為有序數列，直到所有子數列都合併完成，最後變成一個由小至大排的有序數列。

合併排序法優缺點

• 優點： 適合處裡大數據、屬穩定排序。

• 缺點：子數列需額外儲存空間，空間複雜度O(n)。

穩定排序

相等元素，在排序後其相對位置不變。假設有一對雙胞胎大A跟小A，原來的座位順序為大A、小吉、小A、小哇，經過排序後的順序為小吉、小哇、大A、小A，可以發現大A、小A仍然是原來的順序沒有被交換，這就叫穩定排序。因為元素相等做交換沒意義，所以穩定排序不做沒意義的事，如果你想用一個排序法，裡面的每個步驟都有意義，就可以選擇穩定的排序法，如合併排序。

時間與空間複雜度

合併排序法的時間與空間複雜度

合併排序法舉例

1. 分割（divide）

(1). 假設有一個數列

[38, 27, 43, 3, 9, 82, 10]。

(2). 做分割得

[38, 27, 43], [3, 9, 82, 10]。

(3). 對左子數列[38, 27, 43]做分割得[38],[ 27, 43]。

(4). 對右子數列[ 27, 43]做分割得

[ 27], [43]。

(5). 對步驟2的右子數列[3, 9, 82, 10]做分割得[3, 9], [82, 10]。

(6). 對左子數列[ 3, 9]做分割得

[ 3], [9]。

(7). 對右子數列[ 82, 10]做分割得

[ 82], [10]。

2. 合併（conquer）

(1). 分割後的數列為

[38],[ 27], [43],[ 3], [9],[ 82], [10]。

(2). [38],[ 27], [43]之合併過程，對數列[38],[ 27]兩兩合併為有序數列得[27,38]。

(3). 合併[27,38],[43]比較27<43，比較38<43，得有序數列[27,38,43]。

(4). [ 3], [9],[ 82], [10]之合併過程，

比較3<9 得有序數列[3,9]，

比較10<82得有序數列[10,82]，

依次比較得有序數列[3,9,10,82]。

(5). 合併[27,38,43],[3,9,10,82]

依次比較得有序數列[3,9,10,27,38,43,82]。

常見合併排序題目

• 給一個數列用合併排序排序並輸出結果，參考上例
• 合併兩個已排序數列演算法
• 給定一數列，算其中有多少個逆序對
• 合併排序法的時間與空間複雜度
• 用非遞迴方式實現合併排序
• 檔案合併順序和結果