[Грає музика] 

ДАГ Lloyd: ОК, так що злиття роду є ще одним алгоритмом що ми можемо використовувати, щоб розібратися елементи масиву. Але, як ми побачимо, він отримав дуже принципова різниця від вибору сорту, міхур сортувати і сортування вставками які роблять його дійсно дуже розумний. 

Основна ідея злиття сортування для сортування дрібних масивів а потім об'єднати ці масиви разом, або об'єднати them-- отже name-- в відсортованому порядку. Таким чином, що сортування злиттям робить це, використовуючи інструмент називається рекурсія, що і ми будемо говорити про найближчим часом, але ми не говорили про ще. 

Ось основна ідея сортування злиттям. Сортувати ліву половину масиву, за умови, N більше 1. І те, що я маю на увазі, коли кажу, за умови, N більше, ніж 1, Я думаю, що ми можемо погодитися, що, якщо масив складається тільки з одного елемента, це сортується. Ми не насправді потрібно щоб зробити що-небудь з ним. Ми можемо просто оголосити його бути відсортовані. Це всього лише один елемент. 

Так псевдокод, знову ж, сортувати ліву половину масиву, потім відсортувати права половина масив, а потім об'єднати дві половинки разом. Тепер, вже ви могли б бути думаючи, що це начебто тільки Схоже, ви відкладали the-- Ви насправді не роблять нічого. Ви говорите впорядкувати ліву половина, сортувати праву половину, але ти не говориш мені, як ти це робиш. 

Але пам'ятайте, що поки масив є єдиним елементом, ми можемо оголосити його сортувати. Тоді ми можемо просто об'єднати їх разом. І це насправді Основна ідея позаду сортування злиттям, це розбити його таким чином, що Ваші масиви мають розмір одного. І тоді ви відновити звідти. 

Злиття роду, безумовно, складний алгоритм. І це також трохи складніше візуалізувати. Так, ми сподіваємося, візуалізація, що я є тут, допоможе Вам слідувати уздовж. І я буду намагатися з усіх сил, щоб розповісти речі і пройти через це трохи більше, повільніше, ніж інших просто ми сподіваємося отримати вашу голову навколо ідей, що лежать сортування злиттям. 

Отже, ми маємо той же масив в якості інші алгоритм сортування відео якщо ви бачили them-- Масив шостій елемент. І наша псевдокод тут код є свого роду ліва половина, сортувати праву половину, об'єднати дві половинки разом. Отже, давайте це дуже темно червона цегла масиву і відсортувати ліву половину. 

Так на даний момент, ми збираємося ігнорувати речі праворуч. Це там, але ми не так на цьому кроці ще. Ми не Сортування Права половина масиву. Ми в той лівого половина масиву. І тільки заради бути трохи більш ясно, так що я можу звернутися на те, що крок ми на, Я збираюся переключити Колір цього набору апельсина. Тепер, ми все ще говоримо про ж ліва половина вихідного масиву. Але я сподіваюся, що, будучи в стані см кольори різних предметів, це зробить його трохи більш ясно, що тут відбувається. 

ОК, так що тепер у нас є три елементи масиву. Як ми сортуємо ліву половину цього Масив, який до цих пір цей крок? Ми намагаємося, щоб відсортувати ліву половина з червоної цегли array-- ліва половина якого Я тепер пофарбовані в оранжевий колір. 

Ну, ми могли б спробувати повторити цей процес знову. Таким чином, ми все ще в Середина намагаючись розібратися ліва половина повної масиву. Ліва половина Масив, я тільки збираюся довільно вирішувати, що ліва половина буде менше, ніж у правій половині, тому що це відбувається з складається з трьох елементів. 

І тому я хочу сказати, що ліва половина лівій половині масиву це просто елемент п'ять. П'ять, будучи один елемент Масив, ми знаємо, як розбиратися. І так п`ять сортується. Ми просто заявити, що. Це один елемент масиву. 

Таким чином, ми в даний час упорядковано ліва половина лівої half-- вірніше, ми відсортовані ліва половина апельсина. Так що тепер, для того, щоб як і раніше повна ліва половина загального масиву, ми повинні розібратися в праву половину апельсина, або цей матеріал. Як ми це робимо? Ну, у нас є масив з двох елементів. Таким чином, ми можемо впорядкувати ліву половину масиву, який два. Два це єдиний елемент. Так що це сортується за замовчуванням. Тоді ми можемо впорядкувати праву половину тієї частини масиву, один. Це свого роду за замовчуванням. 

Тепер це в перший раз ми досягли крок злиття. Ми завершили, хоча ми тепер вид вкладених down-- і це свого роду хитрий що з рекурсії, Ви повинні тримати голову про те, де ми знаходимося. Таким чином, ми свого роду зліва половина оранжевого частини. 

І тепер, ми знаходимося в середині сортування права половина оранжевого частини. І в цьому процесі, ми тепер збирається бути на крок, об'єднати дві половинки разом. Коли ми дивимося на дві половини масиву, ми бачимо два і один. Який елемент менше? Один. 

Тоді, який елемент менше? Ну, це два або нічого. Так що це два. Так що тепер, просто знову кадр де ми знаходимося в контексті ми упорядковано ліва половина апельсина а права половина походження. Я знаю, що я змінив кольору знову, але це, де ми були. І причина Я зробив це в тому, що цей процес продовжувати йти, повторюючи вниз. Ми відсортували лівий половина колишнього помаранчевого а права половина колишнього помаранчевого кольору. 

Тепер нам потрібно об'єднати тих, дві половинки разом теж. Це крок, який ми зараз перебуваєте. Таким чином, ми розглянемо всі з елементи, які в даний час є зелений, ліва половина вихідного масиву. І ми об'єднуємо тих, використовуючи той же самий процес ми зробили для об'єднання двох і один тільки момент тому. 

Ліва половина, найменший елемент на лівій половині п'ять. Найменша елемент на права половина є одним. Який з них є менше? Один. 

Найменша елемент на ліва половина п'ять. Найменша елемент на права половина це два. Що найменше? Два. І тоді, нарешті, п'ять нічого, ми можемо сказати, п'ять. 

Отже, картина, давайте перерву на секунду і з'ясувати, де ми знаходимося. Якби ми почали з на самому початку, ми Тепер завершені загальна масив тільки один крок коду псевдокоду тут. Ми упорядковано ліва половина масиву. 

Нагадаємо, що оригінальний Наказ був п'ять, два, один. Йдучи через цей процес та гніздування вниз і повторювати, продовжуючи порушувати проблему на більш дрібні і більш дрібні частини, ми вже завершили крок один з псевдокоду протягом усього початковій масиву. Ми розібралися ліву половину. 

Так що тепер давайте заморозити там. А тепер давайте розберемося право половина вихідного масиву. І ми збираємося зробити це, переживає те ж саме ітеративний процес руйнування речі вниз , А потім об'єднувати їх разом. 

Таким чином, ліва половина з червоний або ліва половина правої половини початкового Масив, я збираюся сказати, три. Знову ж таки, я тут бути послідовним. Якщо у вас є непарне Кількість елементів, його насправді не має значення, Ви робите ліва менше або право поменше. 

Важливо те, що всякий раз, коли вам зіткнулися з цією проблемою в проведенні злиття, вам потрібно бути послідовним. Ви або повинні завжди зробити ліва сторона менше або завжди потрібно зробити права сторона менше. Тут я вибрав, щоб завжди зробити ліва сторона менше коли мій масив, чи мій суб-масиву, є непарною розміру. 

Три є один елемент, і тому він відсортований. Ми використовувала це припущення протягом всієї нашої процесі досі. Так що тепер давайте розберемося право половина правій половині, або права половина червоного. 

Знову ж таки, ми повинні розділити це вниз. Це не єдиний елемент масиву. Ми не можемо оголосити його сортувати. І так по-перше, ми збираємося сортувати ліву половину. 

Ліва половина один елемент, так що це свого роду за замовчуванням. Тоді ми йдемо, щоб відсортувати право половина, що один елемент. Це упорядковано за замовчуванням. А зараз, ми можемо об'єднати ці два разом. Чотири менше, і потім шість менше. 

Знову ж таки, те, що ми зробили в цей момент? Ми відсортували лівий половина правій половині. Або повернутися до оригіналу кольору, які були там, ми відсортували лівий половина м'якого червоного. Спочатку він був темно-цегла червоний і тепер це м'якше червоний, чи це була м'якше червоний. 

А потім ми упорядковано Права половина м'якого червоного. Тепер, добре, вони зелені знову, тільки тому що ми збираємося через процес. І ми повинні повторити це знову і знову. 

Так що тепер ми можемо об'єднати тих, дві половинки разом. І це те, що ми робимо тут. Так чорної лінії тільки розділити ліву половину а права половина цього роду частини. 

Ми порівнюємо найменше значення на лівій стороні array-- або, вибачте, найменша Значення лівій половині найменшому значенню права половина і виявили, що три менше. А тепер трохи оптимізації, вірно? Там насправді нічого залишили на лівій стороні. 

Там немає нічого решта на лівій стороні, тому ми можемо ефективно просто move-- ми можемо оголосити решта насправді сортуються і тільки лавірувати його на, тому що немає нічого ще для порівняння. І ми знаємо, що права сторона з правого боку сортується. 

ОК, так що тепер давайте знову і заморозити з'ясувати, де ми знаходимося в історії. У загальному масиві, Що ми зробили? Ми насправді виконати Тепер кроки одне і другий етап. Ми відсортували ліву половину, і ми відсортували праву половину. 

Так що тепер, все, що залишається для нас об'єднати ці дві половинки разом. Таким чином, ми порівнюємо найнижчий цінується елемент кожній половині масиву у свою чергу, і продовжити. Одним з них є менш ніж три, так що йде. 

Два менше трьох, так що два йде. Три менш ніж 5, так три йде. Чотири менше, ніж 5, так четвірка заходить. Тоді п'ять менше, ніж шостій, і шість це все, що залишається. 

Тепер, я знаю, що було багато кроків. І ми залишили багато пам'яті в нашій хвилі. І це те, що ці сірі квадрати. І це, ймовірно, відчував, що це взяв набагато довше, ніж вставки роду, міхур сортувати, або вибір роду. 

Але насправді, тому що Багато з цих процесів відбуваються в той же time-- що те, що ми будемо, знову ж таки, говорити, коли ми говоримо про рекурсія в майбутньому video-- цей алгоритм насправді ясно принципово відрізняється від усього, ми бачили раніше але також значно більш ефективним. 

Чому так? Ну, в гіршому сценарій, у нас є розділити п елементів до а потім зливають. Але коли ми возз'єднати їм, що ми робимо в основному подвоєння Розмір менших масивів. У нас є купа одного елемента масиви, які ми ефективно об'єднати в двох масивах елементів. А потім ми візьмемо тих, два масиви елемент і об'єднати їх разом в чотирьох масиву елементів, і так далі, ні і так далі, і так далі, до тих пір, є один масив п елементів. 

Але скільки подвоєння це, щоб дістатися до п? Згадайте, наприклад телефонної книги. Скільки разів ми повинні рвати телефонна книга на половину, скільки ще раз ми повинні рвати телефонну книгу навпіл, якщо розмір телефонної книги в два рази? Там тільки один, вірно? 

Так що якась логарифмічна елементом тут. Але ми також все ще є, принаймні дивитися на все п елементів. Таким чином, в гіршому випадку, сортування злиттям працює в п журналу п. Ми повинні дивитися на всі п елементів, і ми повинні об'єднати їх разом в журналі н наборів кроків. У кращому випадку, масив прекрасно відсортовані. Це чудово. Але на основі алгоритму ми маємо тут, ми все ще повинні розділити, а потім. Хоча в цьому випадку рекомбінуючих начебто неефективними. Вона не потрібна. Але ми як і раніше йти через весь процес в будь-якому випадку. 

Таким чином, в кращому випадку а в гіршому випадку, цей алгоритм працює в журналі н н часу. Злиття роду, безумовно, трохи складніше ніж інших основних алгоритмів сортування ми говорили про CS50, але істотно більш потужним. 

І тому, якщо ви коли-небудь знайти Приводом для це потрібно або використовувати його для сортування великий набір даних, отримання Ваша голова навколо ідеї рекурсії буде дуже потужний. І це буде зробити свій програми дійсно набагато ефективніше за допомогою сортування злиттям проти що-небудь ще. Я Дуг Ллойд. Це CS50.