關於合併排序代碼中的合併步驟的困惑

Question

我對如何在數組上合併排序有效。 我明白'劃分'步驟，它將輸入數組劃分爲1長度元素。但是，當談到'合併'部分（合併步驟）時，我感到困惑。 例如，給定輸入3 5 1 8 2，除法過程將導致5個元素：3,5,1,8,2。我只理解合併函數將它們合併爲3 5，1 8，2，但它如何繼續合併3 5和1 8？ 「組合」部分涉及到遞歸嗎？

Answer 1

當兩個遞歸排序例程返回時，可以安全地假定他們已經排序了它們的部分。合併步驟結合了這兩個排序的子數組。如果輸入是3 5 1 8 2，則第一次遞歸調用將對前半部分進行排序併產生3 5，第二次遞歸調用將對後半部分進行排序併產生1 2 8。現在，合併步驟通過重複選擇兩個子數組中的兩個第一個元素的最小值並將其添加到結果中，將這兩個已排序的半部合併爲一個。

該過程就像感應。

Answer 2

這個動畫應該可以幫到你。

http://en.wikipedia.org/wiki/File:Merge-sort-example-300px.gif

的過程是這樣的：

3，5，1，8,2

3 5，1 2 8

1. 從n個輸入項目的未排序列表I開始。
2. 將I分爲兩部分I1和I2，分別爲天花板（n/2）和地板（n/2）。
3. 遞歸排序I1，產生排序列表S1。
4. 遞歸排序I2，產生排序列表S2。
5. 合併S1和S2成排序的列表S.

在每次迭代中，選擇具有從兩個輸入列表最小鍵的項目，並將其附加到輸出列表。由於兩個輸入列表已排序，因此只有兩個項目可用於 測試，因此每次迭代需要一定的時間。