[音樂播放] 

DOUG LLOYD：OK，這樣的合併 排序是另一種算法 我們可以用它來梳理 數組的元素。 但是，正如我們看到的，它有一個 很根本的區別 從選擇排序，冒泡 排序和插入排序 這使得它真的很聰明。 

合併背後的基本理念 排序是更小的數組排序 然後再結合這些陣列 在一起，或合併them-- 因此，在有序的name--。 該歸併排序的方式做 這是通過利用一個工具 被稱為遞歸，這是什麼 我們要談論不久， 但我們還沒有真正談過呢。 

這裡的背後歸併排序的基本思想。 對數組進行排序的左半部分， 假設n大於1。 而我的意思是，當我說 假設n大於1是 我想我們可以同意，如果一個數組 僅由一個單一的元件的， 它的排序。 我們實際上並不需要 做任何事情來了。 我們只需將其聲明進行排序。 這只是一個單一的元件。 

這樣的偽碼，同樣，是 對數組進行排序的左一半， 然後排序右半陣列， 然後合併兩半。 現在，已經你可能會 思考，它只是一種 聽起來你推遲喜歡the-- 你實際上沒有做任何事情。 你是說左邊的排序 上半年，排序的右半​​部分， 但你不能告訴 我怎麼你這樣做。 

但要記住，只要 陣列是一個單一元件， 我們可以宣布它排序。 然後，我們就可以將它們組合在一起。 而這實際上是 背後歸併排序基本思想， 是要打破它，這樣 你的數組的大小之一。 然後你從那裡重建家園。 

合併排序是肯定 一個複雜的算法。 而且它也是一個小 複雜的可視化。 所以希望，可視化，我 這裡將幫助你跟著。 我會盡我所能敘述的事情 並繼續通過這個多一點 慢慢比其他的 只是希望得到你的頭 各地背後歸併排序的思想。 

因此，我們有相同的陣列作為 其他排序算法視頻 如果你看過them-- 六元素的數組。 在這裡，我們的偽代碼排序 左半，排序右半 合併的兩半一起。 因此，讓我們利用這個非常暗磚紅色 數組和排序它的左半邊。 

所以暫且，我們將 忽略右邊的東西。 它的存在，但我們 不是在這一步呢。 我們不是在排序 陣列的右半。 我們在左邊的排序 一半的陣列。 而貪圖 被多一點 清晰的，這樣我就可以參考 到了哪一步，我們是上， 我要去切換 顏色這套橙色的。 現在，我們還在談論 原來陣列相同的左一半。 但我希望，通過能夠 指各種物品的顏色， 它會讓它多了幾分 不清楚什麼是怎麼回事。 

好了，現在我們有一個 三元數組。 我們怎麼樣的這個左半 陣列，這仍然是這個步驟？ 我們試圖向左排序 一半的磚紅色array--的 其中左一半 我現在已經橙色。 

好了，我們可以嘗試 再次重複這個過程。 因此，我們仍然在 試圖梳理中間 完整陣列的左半部。 的左半 陣列，我只是去 任意決定的左半 將比右半較小， 因為這恰巧 包括三個部分。 

所以我會說， 左半陣列的左半 只是五行說。 五，作為一個單一的元素 陣列，我們知道如何排序。 所以五是排序。 我們只是要聲明。 這是一個單元素數組。 

所以，我們現在已經排序 左half--的左半 或者更確切地說，我們已經排序 橙色的左半部。 所以，現在，為了仍然完整 整個陣列的左半邊， 我們需要的右半排序 的橙色或這個東西。 我們該怎麼做呢？ 好了，我們有兩個元素的數組。 因此，我們可以排序的左半 陣列，這是兩個。 兩個是單一元件。 因此，它的排序默認情況下。 然後，我們可以排序的右半 該部分陣列，所述一個的。 這類型的默認。 

現在這是第一次 我們已經達成了合併的步驟。 我們已經完成了，雖然 那種我們現在嵌套down-- 這就是那種棘手的 遞歸的是， 你需要保持你的 腦袋一下我們在哪裡。 因此，我們在左邊的已排序 一半的橙色部分。 

而現在，我們在整理的中間 橙色部的右半部分。 而在這過程中，我們 現在即將要上台階， 合併的兩半一起。 當我們在看的兩半 陣列的，我們看到兩個和一個。 該元件是小？ 一。 

那麼哪一個元素是小？ 嗯，這是兩個或沒有。 因此，這兩種。 所以，現在，想再次回到框架 我們所處的背景下， 我們已經整理了 橙色的左半 和原點的右半部。 我知道我已經改變了顏色 再次，但是這就是我們。 而我之所以這樣做 是因為這個過程是 要繼續下去，迭代下降。 我們已經排序的左 半前橙色 和前橙色的右半部分。 

現在，我們需要合併這些 兩半了。 這是我們的第一步。 所以我們考慮所有的 元素是現在綠， 原數組的左半部。 我們合併這些 使用相同的過程 我們為合併兩個 和一個剛才。 

左半，最小 左邊一半元件是五。 上的最小元素 右半邊是其中之一。 其中哪些是小？ 一。 

上的最小元素 左半邊是五。 上的最小元素 右半邊為兩個。 什麼是最小的？ 二。 然後最後五 什麼都沒有，可以說五位。 

好了，這麼大的畫面，讓我們 休息一秒鐘 並找出我們在哪裡。 如果我們從開始 一開始，我們 現在已經完成了 整體陣列只 的偽代碼一步在這裡。 我們已經整理了 陣列的左半部。 

回想一下，原 為了五歲，二，一。 通過經歷這個過程 和築巢下來，重複， 繼續打破問題 分解成更小和更小的部分， 現在我們已經完成 步驟的偽代碼之一 對於整個起動陣列。 我們已經整理了左前衛。 

所以，現在，讓我們定格在那裡。 現在，讓我們來排序的權利 原來的一半數組。 而我們要做到這一點 經歷同樣的迭代 打破下來的過程 然後將它們合併在一起。 

這樣的左半 紅色，或左半 原稿的右半部 陣，我會說是三。 再次，我是一致的在這裡。 如果你有一個奇怪的 元件的數目，它 並沒有真正也罷 你讓左邊的一個小 或者是正確的要小。 

重要的是，只要你 遇到在進行這個問題 合併，就需要保持一致。 要么你總是需要 使一個左側小 或總是需要使 右側小。 在這裡，我選擇永遠 使左側小 當我的數組，還是我的 子陣列，是一個奇怪的大小。 

三是單一元件， 所以它的排序。 我們充分利用這一假設 我們整個過程為止。 所以，現在讓我們來排序的權利 一半的右邊一半的， 或紅色的右半邊。 

同樣，我們需要拆分下來。 這不是一個單一的元件陣列。 我們不能宣布它排序。 所以首先，我們要 在左半排序。 

左半是單一元件， 所以它的排序默認情況下。 然後，我們要排序的權利 一半，這是單一元件。 它的排序默認情況下。而現在， 我們可以合併這兩個在一起。 四個較小，並 然後6越小。 

此外，我們還有什麼在這一點上做了什麼？ 我們已經排序的左 一半的右邊一半。 或回到原來的 這是有顏色的， 我們已經排序的左 一半的較軟的紅色。 它最初是一個黑磚 紅現在是一個更柔和的紅色， 或者，這是一個較軟的紅色。 

然後我們排序 的較軟紅右半邊。 現在的，很好，他們是綠色還是一樣，只 因為我們正在經歷一個過程。 我們要重複 這一遍又一遍。 

所以，現在，我們可以合併這些 兩半。 這就是我們在這裡做。 所以黑線剛 劃分左半 與這種部分的右半部分。 

我們比較的最小值 在array--左側 還是原諒了我，最小 左半的值 到的右側的值最小 一半，並找到三個較小。 而現在有點優化的，對不對？ 有其實也沒什麼 留在左側。 

沒有什麼剩餘 在左側， 所以我們可以有效地 只是move--我們可以聲明 它的其餘部分實際上是 排序，只是它釘住 對，因為沒有什麼 別人進行比較的。 我們知道，右側 右側是排序。 

好了，現在讓我們再次凍結和 找出我們所處的故事。 在整個陣列， 我們有什麼成就？ 我們實際上已經完成 現在步驟一和步驟二。 我們的排序左半，和 我們整理了右半邊。 

所以，現在，這一切仍然是我們 這些兩半合併在一起。 所以我們比較具有最低值 陣列的每個一半的元件 反過來，然後繼續。 一個是小於3，所以一去。 

二是不到三年，所以二除。 三是小於5，所以三去。 四是小於5，因此四去。 然後，五是不到六個月， 六是所有仍然存在。 

現在，我知道，這是一個很大的步驟。 而且我們留下了很多 記憶在我們喚醒。 而這正是那些灰色方格。 它可能感覺就像是拿了 很多的時間比插入排序，氣泡 排序或選擇排序。 

但實際上，由於 很多這些過程 都發生在同一時間 -  這是一件好事，我們將再次 談論當我們談論 遞歸在未來video-- 這種算法實際上 顯然是根本 比什麼不同 我們已經看到前 但是也顯著 更有效。 

這是為什麼呢？ 那麼，在最壞的 的情況下，我們有 分裂n個元素了 然後重新組合它們。 但是，當我們重新組合 他們，我們在做什麼 基本上是翻倍 較小的數組的大小。 我們有一大堆的一個元素 陣列我們有效 合併成2個元素的數組。 然後我們把這些 二元陣列 並結合在一起成 4元件陣列，等等， 等等，依此類推，直到我們 有一個單個n元件陣列。 

但究竟有多少倍增 它才能讓到n？ 回想一下電話簿的例子。 多少次，我們要撕 電話薄了一半，要多 次我們是否撕電話簿 在一半中，如果電話簿的大小 翻倍？ 這裡只有一個，對不對？ 

因此，有某種 這裡對數的元素。 但是，我們也還是要至少 看看所有的n個元素。 因此，在最壞的情況下， 合併排序運行時間為n日誌ñ。 我們來看看 所有的n個元素， 我們必須把它們混合起來 一起在記錄n個步驟。 在最好的情況下， 該陣列是完全排序。 這是偉大的。 但基於算法，我們這裡有， 我們還是要分裂和重組。 雖然在這種情況下， 再結合是一種無效的。 它是不需要的。 但是，我們仍然要經過 整個過程呢。 

因此，在最好的情況下 而在最壞的情況下， 該算法運行在的n log n次。 合併排序肯定是有點棘手 比其他主排序算法 我們談到CS50但 實質上更加強大。 

所以，如果你發現 有時需要它 或用它來排序 大型數據集，得到 你的頭左右遞歸的想法 將是真正強大。 而這將讓你的 節目真的更有效 使用分類合併與其他任何東西。 我是道格·勞埃德。 這是CS50。