[Powered by Google Translate] [歸併排序] [羅布·鮑登 - 哈佛大學] [這是CS50。 -  CS50.TV] 讓我們來談談有關合併排序。 到目前為止，您已經看到冒泡排序，插入排序，選擇排序。 雖然我種我的手，我的意思更好地波， 合併排序通常執行比這3類。 

但在談論合併排序之前，讓我們來談談關於合併的2個排序的列表。 我們會給你打電話的過程中，2排序的列表，像這樣的， 使一個單一的排序列表中的他們 - 合併列表。 如何才能做到這一點呢？ 好了，一個想法，就是堅持一個列表到其他列表 ，然後在結果列表進行排序。 

雖然這個工作，這是一個許多不必要的工作。 我們可以做得更快比剛排序。 請注意，一個錯誤的觀念，是採取交替杯，從每個列表中。 雖然這可能看起來像這樣的作品，在第一， 這樣做，我們最終4，8，15，23，16  - 通知，16日和23出來的地方。 這是因為，在合併後的名單應該會出現連續的2個元素 是在相同的初始列表。 15和16都在左側列表中的。 關鍵是要充分利用已排序的事實，這兩個列表。 這意味著，如果我們只是看在兩個列表中的第一個元素 -  在這裡，4和8  - 其中之一也必須合併後的列表中的第一個元素。 好了，這是為什麼？ 這兩個列表都已經排序， 等4個或8時，必須是最小的元素，我們結合2列出了。 在這種情況下，最小的是4， 因此，我們可以拿出4，我們的合併列表中的第一個元素。 現在我們將繼續合併剩餘的3個元素​​的第一個列表 和4個元素的第二列表。 

再次，我們只需要看看這兩個列表中的第一個元素。 中的較小者的2必須是我們的合併列表中的第二個元素。 這一次，8和15之間，最小的是8，所以我們插入， 作為我們的排序的列表的第二個元素。 我們可以繼續比較這兩個列表中的第一個元素 並除去2的小的。 15日和23日，15相比較小，所以這是我們的第三個元素。 現在比較16和23中，圖16是較小的。 所以這是第四個元素。 

請注意，2個元素是從同一個列表中的行。 這是為什麼合併後的清單不能只是備用2個列表元素。 比較50和23，23小，所以我們選擇。 在50和42之間，42是較小的。 在50和108之間，50是較小的。 最後，我們只是有108個，所以一定要在我們的名單。 請注意，我們有一個很好的，排序的列表。 每次我們比較了2列出了前2個元素 我們能夠確定合併後的列表中的下一個元素。 這意味著，如果最終的列表包含n個號碼，其中，n是8， 然後，我們需要在最n次比較這些數字放到合適的地方。 這樣的算法的所述以線性時間運行， 不過不用擔心，在這裡。 

使用我們的算法進行合併，我們就可以進行快速的合併排序算法。 所以，讓我們的名單重置。 歸併排序的過程中，有2個大的步驟。 首先，連續分裂列表杯分為兩半 直到我們有一堆名單，他們只用1杯。 不要擔心，如果列表中包含一個奇數 你不能讓他們之間的一個完全乾淨的切割。 只需隨便挑哪一個清單，包括額外的杯子中。 所以，讓我們這些列表拆分。 現在，我們有2個列表。 現在，我們有4個列表。 

現在，我們有8個列表，每個列表中的單杯。 所以這是它的第1步。 對於第2步，我們多次合併對使用合併算法，我們以前學過的列表。 合併108和15，我們結束了15日，108。 ，合併50和4，我們最終有4個，50。 合併8和42，我們有8個，42。 合併23和16，我們最終有16個，23。 現在我們的列表大小為2。 請注意，每個的4列出的是排序條件。 

因此，我們可以再次開始合併對列表。 合併15和108以及4和50  -  先來的4個，然後是15，然後是50，然後是108。 合併8，42，16，23， 我們先來的8個，然後16，然後23，然後42。 所以現在我們有2列出了大小為4，每一個排序。 所以，現在我們合併這兩個列表。 首先，我們採取了4。 然後，我們採取了8。 然後我們把15和16，然後23，然後42，然後50，然後108。 我們就大功告成了。 我們現在有一個排序的列表。 因此，如何快速是這樣的，到底是什麼？ 在技​​術方面，歸併排序是O（n日誌n）， 而所有的冒泡排序，插入排序，選擇排序為O（n²）。 事實上，你會學習很快，你將不能夠拿出一種 執行在一般情況下比O（n日誌n）。 再次，不要擔心這個大O表示法，如果你還沒有看到它。 

只知道，這意味著如果我們想要，排序一個真正的大名單 冒泡排序，插入排序，選擇排序可能 明顯長於合併排序。 這並不意味著會更快歸併排序的所有列表 甚至是任何單獨的列表中下一個一定規模的。 例如，插入排序可能是最快的排序為所有小於5個元素的列表。 在實踐中，合併排序通常更快盡可能小為50個元素的列表。 

但這些額外的速度不會沒有代價的。 與其他各種不同的是，一個列表，修改列表中的地方 直到我們得到一個排序的列表，歸併排序需要一些額外的空間 合併2列出了一起。 我們不能立即使用的名單，被合併存儲合併列表 因為我們可能會覆蓋仍需要合併的元素。 這個空間是一個位的價格，但它通常是不講理的。 這就是歸併排序。 

我的名字是羅布·波頓，這是CS50。 [CS50.TV]  - 選擇排序。 [笑] 哦，得了採取的太多，因為我交換，我是如何呈現它。 在左側的列表。這是一個錯字。 [misspoke我搞砸了 -  [笑] 我不知道是什麼 -