檔案合併順序和結果

 有 6 個已排序過的檔案，長度分別為 7，9，2，3，6，13。這 6 個檔案經過 5 次的

兩兩合併，成為一個完整排序過的檔案。已知合併時間複雜度與兩個合併檔案的

長度和成正比，請用 merge tree 寫出他們的合併順序與結果，且 merge tree 的 left 

subtree 長度小於 right subtree。

答

因合併時間複雜度與檔案長度和成正比，故優先選兩檔案長度小做合併，可確保總時間最小。

已排序過的檔案長度為 [7, 9, 2, 3, 6, 13]，需使用 5 次合併來完成。

1. 第一次合併：2 和 3 合併為 5

2. 第二次合併：5 和 6 合併為 11

3. 第三次合併：7 和 9 合併為 16

4. 第四次合併：11 和 13 合併為 24

5. 第五次合併：16 和 24 合併為 40

最後合併順序與結果如下：

            40

             /  \

           16    24

          /  \   /  \

         7    9 11   13

             / \

            5   6

           / \

          2   3