>> [音樂播放]
>> 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。