[За възпроизвеждане на музика] 

Дъг LLOYD: ОК, така че сливането сортирай е още един алгоритъм че можем да използваме, за да се оправи елементите на масив. Но както ще видим, тя има много съществена разлика от селекция сортиране, балон сортиране и сортиране чрез вмъкване които го правят наистина доста умен. 

Основната идея зад сливат сортирай е да се справи по-малки масиви и след това да се съчетаят тези масиви заедно, или да се слеят them-- оттам name-- в сортиран ред. Начинът, по който се слеят подреди прави това е като използваме инструмент нарича рекурсия, което е това, ние ще трябва да се говори за най-скоро, но не сме говорили за още. 

Ето основната идея за сливане на сортиране. Подреди лявата половина на масива, предположи, п е по-голямо от 1. И това, което искам да кажа, когато казвам предположи, п е по-голямо от 1 е, Мисля, че можем да се съгласим, че ако масив само се състои от един елемент, това е сортирани. Ние всъщност не се нуждаете да се направи нещо за него. Ние можем просто да я обяви за да се сортира. Това е само един елемент. 

Така че Псевдокод, отново, е сортирате лявата половина на масива, След сортирате дясната половина на масива, след това се сливат двете половини заедно. Сега вече може да сте мисли, той просто вид звучи като сте отлагах the-- не сте всъщност прави нищо. Искаш да кажеш, сортирате отляво половината, сортирате дясната половина, но вие не казвате ми как го правиш. 

Но не забравяйте, че най-дълго масив е един елемент, можем да я обяви сортирани. Тогава ние можем просто да ги комбинирате заедно. И това е всъщност най- фундаментална идея зад сортиране чрез сливане, е да го съборят, така че масивите са с размер на една. И тогава ще се възстанови от там. 

Обединяване на сортиране е определено сложен алгоритъм. И това също е малко сложно да се визуализира. Така че да се надяваме, че визуализацията I имаме тук ще ви помогне да следват заедно. И аз ще направя всичко възможно да разкажа неща и да преминат през това малко по- бавно от други такива само да се надяваме да получите главата си около идеите зад сортиране чрез сливане. 

Така че ние имаме един и същ масив като други сортиране алгоритъм видеоклипове ако сте виждали them-- шест масив. И нашата Псевдокод код тук е нещо лявата половина, сортирате дясната половина, слее двете половини заедно. Така че нека да се възползвам от тази много тъмно червена тухла масив и сортиране на лявата половина на него. 

Така че за момента, отиваме да не обръща внимание на неща от дясно. Той е там, но ние сме не на още тази стъпка. Ние не сме най-сортиране на дясната половина на масива. Ние сме най-подредени отляво половината от масива. И само заради да бъде малко по- ясна, така че може да се отнася до каква крачка сме на, Отивам да превключите Цвят на този комплект до оранжево. Сега, ние сме все още говорим за същото лявата половина на оригиналния масив. Но аз се надявам, че като е в състояние да вижте цветовете на различни позиции, това ще стане малко по- ясно какво става тук. 

ОК, така че сега имаме три масив. Как ще се справи в лявата половина на тази масив, който е все още на този етап? Ние се опитваме да сортирате отляво половината от червена тухла array-- лявата половина на който Аз бях вече оцветени в оранжево. 

Е, можем да се опитаме да този процес се повтаря отново. Така че ние сме все още в средна опитва да подреди лявата половина на пълния набор. Лявата половина на масив, аз съм просто ще произволно да решат, че лявата половина ще бъде по-малък от дясната половина, защото това се случва с се състои от три елемента. 

И така, аз отивам да се каже, че лявата половина на лявата половина на масива е само елемент пет. Five, бидейки един елемент масив, ние знаем как да го оправи. И така пет се сортира. Ние просто ще декларирам, че. Това е един елемент масив. 

Така че ние сега сме сортирани по лявата половина на лявата half-- или по-скоро, ние сме сортирани по лявата половина на портокала. Така че сега, за да все още пълно лявата половина на цялостната масива, ние трябва да се справи със дясната половина от портокала, или тези неща. Как да го направим? Е, ние имаме две масив. Така че можем да сортирате лявата половина на масива, което е две. Две е един елемент. Така че това е сортирани по подразбиране. Тогава можем да сортирате дясната половина от тази част на масива, онзи. Това е нещо като по подразбиране. 

Това сега е първият път, ние сме достигнали етап на сливане. Имаме реализирани, въпреки че ние сега вид вложени down-- и това е нещо като Tricky нещо с рекурсия е, вие трябва да поддържате глава за това къде сме. Така че ние сме нещо като ляво половината от оранжево част. 

И сега, ние сме в средата на сортиране дясната половина на оранжевата част. И в този процес, ние сме Сега на път да бъде по стъпка, слее двете половини заедно. Когато погледнем към двете половини на масива, виждаме две и една. Кой елемент е по-малък? One. 

Тогава кой елемент е по-малък? Е, това е два или нищо. Така че това е две. Така че сега, само за да оформи отново къде сме ние в контекст ние сме сортирани по лявата половина на портокала и дясната половина на произхода. Знам, че съм променил цветовете отново, но това е, когато сме били. И причината Направих това е така, защото този процес е ще продължи да функционира, итерации надолу. Ние сме подредени отляво половината от бившия портокала и дясната половина на бившата портокала. 

Сега, ние трябва да се слеят тези, две половини заедно също. Това е етапът, че сме на. Така че ние считаме, всички от елементи, които сега са зелени, лявата половина на оригиналния масив. И ние се слеят тези, като се използва същият процес направихме за сливане на две и преди една само за миг. 

Лявата половина, най-малките елемент в лявата половина е пет. Най-малкият елемент на дясната половина е един. Коя от тях е по-малък? One. 

Най-малкият елемент на лявата половина е пет. Най-малкият елемент на дясната половина е две. Какво е най-малката? Two. И тогава накрая пет и нищо не можем да кажем, пет. 

ОК, така че голяма картина, нека си вземе почивка за секунда и да разбера къде сме. Ако ние започнахме от самото начало, ние сега са завършили за общата масив просто една стъпка от кода на Псевдокод тук. Ние сме сортирани по лявата половина на масива. 

Припомнете си, че оригиналът За да е пет, две, едно. Чрез става чрез този процес и гнездене надолу и повтаряне, продължава да се прекъсне проблема на по-малки и по-малки части, ние сме вече приключи стъпка един от Псевдокод за целия изходен масив. Ние сме сортирани лявата му половина. 

Така че сега нека да замрази там. А сега нека да сортирате правото половината от оригиналния масив. И ние ще направим това с преминавайки през една и съща итеративен процес на разчупване на нещата и след това да ги сливат заедно. 

Така че лявата половина на червено, или лявата половина на дясната половина на оригинала масив, аз отивам да се каже, е три. Отново, аз съм тук, за да бъде последователна. Ако имате нечетен брой елементи него, няма значение дали направите остави един малък или най-подходящия малък. 

Важното е, че всеки път, когато сблъскате с този проблем при провеждането сливане, което трябва да бъде последователна. Или винаги трябва да направи ляво-малък или винаги трябва да се направи От дясната страна-малък. Ето, аз съм избрал да винаги направи отляво малък когато моят масив, или ми под-масив, е от нечетен размер. 

Три е един елемент, и така тя се сортира. Ние сме ливъридж това предположение през целия ни процес досега. Така че сега нека да сортирате правото половината от дясната половина, или дясната половина на червено. 

Отново, ние трябва да се раздели този надолу. Това не е един-единствен елемент масив. Ние не можем да я обяви сортирани. И така, първо, отиваме да се справи със лявата половина. 

Лявата половина е един елемент, така че това е нещо като по подразбиране. След това отиваме да сортирате правото половината, която е един елемент. Той е сортирани по подразбиране. И сега, ние можем да се слеят тези две заедно. Четири е по-малък, и След шест е по-малък. 

Отново, това, което направихме в този момент? Ние сме подредени отляво половината от дясната половина. Или се връщам към оригинала цветове, които бяха там, ние сме подредени отляво половината от мек червено. Той първоначално е бил тъмен тухла червено, а сега е по-мек червен, или е по-мек червено. 

И тогава ние сме сортирани по дясната половина на по-мек червено. Сега, добре, те са зелени отново, просто защото ние преминаваме през процес. И ние трябва да се повтаря това отново и отново. 

Така че сега можем да обедините тези, две половини заедно. И това е, което правим тук. Така че черната линия просто разделя лявата половина и дясната половина на този вид част. 

Ние сравняваме най-малката стойност от лявата страна на array-- или да ме извините, най-малките стойност на лявата половина на най-малката стойност на правото половината и откриете, че е по-малък от три. А сега малко на оптимизация, нали? Има всъщност нищо наляво по левия фланг. 

Няма нищо оставащото от лявата страна, Така че ние можем ефективно Просто move-- можем да декларираме останалото е всъщност сортирани и просто го халс нататък, защото няма нищо, друг да сравнявате против. И ние знаем, че от дясната страна от дясната страна се сортира. 

ОК, така че сега да се замразява отново и разбера къде сме в историята. В общата масива, какво сме изпълнили? Ние действително постигнете Сега стъпки една и стъпка две. Ние подредени в лявата половина, и ние сортирани дясната половина. 

Така че сега, всичко, което остава, е за нас да се слеят тези две половини заедно. Така че ние сравнявате най-ниската ценени елемент на всяка половина на масива от своя страна, и се процедира. Един от тях е по-малко от три, така че човек отива. 

Две е по-малко от три, така че два отива. Три е по-малко от 5, така че три отива. Four е по-малко от 5, така че четири отива. След пет е по-малко от шест, и шест е всичко, което остава. 

Сега, аз знам, че е много стъпки. И ние сме оставени много на памет в нашето събуждане. И това е, което тези сиви квадрати са. И това може би се чувствах като че пое много по-дълго, отколкото сортиране чрез вмъкване, балон сортиране, или избор на сортиране. 

Но всъщност, защото Много от тези процеси се случва в същото time-- което е нещо, ние ще, отново, говорим за, когато говорим за рекурсия в бъдещ video-- този алгоритъм всъщност ясно е фундаментално различно от всичко, видяхме преди но също така значително по-ефективно. 

Защо така? Е, в най-лошите лош сценарий, ние имаме да се раздели наш елементи нагоре и след това да ги рекомбинират. Но когато се рекомбинират тях, какво правим груб удвоявайки размер на малки масиви. Имаме един куп един елемент масиви, че ефективно съчетават в две елемент масиви. И тогава ние приемаме тези, две елемент масиви и да ги комбинирате в четириелементови масиви, и така нататък, и така нататък, и така нататък, докато не има едно п масив. 

Но колко удвоявания отнема да стигнем до п? Помислете обратно към примера на телефонния указател. Колко пъти трябва да се скъса телефонния указател на половина, колко още пъти трябва да откъсне телефонния указател наполовина, ако размерът на телефонния указател удвоил? Има само един, нали? 

Така че има някакъв вид логаритмична елемент тук. Но ние също така все още трябва да най-малко Посетете всички п елементи. Така че в най-лошия случай, сортиране чрез сливане работи в п дневник п. Ние трябва да разгледаме Всички N елементи, и ние трябва да ги комбинирате заедно в дневника н набори от стъпки. В най-добрия случай, масива е перфектно подредени. Това е прекрасно. Но въз основа на алгоритъма, което имаме тук, ние все още трябва да се раздели и рекомбинират. Въпреки че в този случай, рекомбиниране е вид неефективна. Това не е необходимо. Но ние все още проверете на целия процес, така или иначе. 

Така че в най-добрия случай и в най-лошия случай, този алгоритъм работи в п дневник п време. Обединяване на сортиране определено е малко по-особено в сравнение с другите основни алгоритми за сортиране ние говорихме за CS50, но е значително по-мощен. 

И така, ако някога намеря повод да се нуждаят от нея или да го използвате, за да се справи с голям набор от данни, получаване главата си около идеята за рекурсия ще бъде наистина мощен. И това се случва, за да си програми наистина много по-ефективно използване на сортиране чрез сливане в сравнение с нещо друго. Аз съм Дъг Лойд. Това е CS50.