[Prehrávanie hudby] 

DOUG LLOYD: OK, takže zlúčenie sort je ďalším algoritmus že môžeme použiť vyriešiť prvky poľa. Ale ako uvidíme, je to dostal veľmi zásadný rozdiel z výber druhu, bublina triediť a insertion sort ktoré robia to naozaj celkom šikovný. 

Základnou myšlienkou zlúčenie triedenie je triediť menších polí a potom spojiť tieto polia dohromady, alebo zlúčiť them-- od tejto doby name-- v zoradení poradí. Spôsob, akým merge sort robí to je využitím nástroja zvanej rekurzia, čo je to, čo budeme hovoriť o skoro, ale my sme naozaj hovoril o doteraz. 

Tu je základná myšlienka zlúčenie druhu. Triediť ľavú polovicu poľa, za predpokladu, že n je väčšie ako 1. A čo mám na mysli, keď hovorím za predpokladu, že n je väčšie ako 1, je, Myslím, že sa zhodneme na tom, že ak pole iba sa skladá z jedného prvku, je to triediť. Nemáme skutočne potrebujú urobiť čokoľvek, aby to. Môžeme len vyhlásiť, že majú byť triedené. Je to len jeden prvok. 

Takže pseudocode, opäť, je zoradiť ľavej polovici poľa, potom triediť pravú polovicu poľa, potom zlúčiť dve polovice dohromady. Teraz už by ste mali byť myslenia, je to len trochu Znie to, ako by si odkladali the-- nie ste naozaj robiť nič. Hovoríš, že triediť ľavý polovici, triediť pravú polovicu, ale ty nehovoríš me, ako to robíte. 

Ale pamätajte si, že kým pole je jeden element, môžeme prehlásiť, že triediť. Potom sa môžeme len spojiť dohromady. A to je vlastne Základnou myšlienkou zlúčenie druhu, je rozobrať to tak, že vaše pole má veľkosť jedného. A potom znova odtiaľ. 

Merge sort je určite komplikovaný algoritmus. A je to tiež trochu zložité predstaviť. Takže dúfajme, vizualizácia, ktoré som tu vám pomôže sledovať spolu. A budem snažiť čo najlepšie rozprávať veci a pokračovať cez to trochu viac pomalšie ako tie ostatné len dúfajme, že si hlavu okolo myšlienok zlúčenie druhu. 

Takže máme rovnaké pole ako The ďalšie triedenie algoritmus videá ak ste videli them-- Array šiestich prvok. A naše pseudokód kód tu je trochu ľavá polovica, triediť pravú polovicu, spojiť obe polovice k sebe. Takže poďme sa tento veľmi tmavo tehlovo červená poľa a triediť ľavú polovicu. 

Takže v súčasnej dobe, ideme ignorovať veci na pravej strane. Je to tam, ale my sme nie na ešte tomto kroku. Nie sme na radiť pravá polovica poľa. Sme na druhu Na ľavej polovica poľa. A len kvôli z toho, že trochu viac jasné, takže môžem odkázať k tomu, čo sme na krok, Budem prepnutie Farba tohto nastavená na oranžovú. Teraz sme stále hovoril o To isté ľavú polovicu pôvodného poľa. Ale ja dúfam, že tým, že je schopný odkazujú na farby rôznych položiek, to bude robiť to o niečo viac jasné, čo sa tu deje. 

OK, takže teraz máme Tri element poľa. Ako môžeme radiť ľavej polovici tohto poľa, čo je stále ešte tento krok? Snažíme sa vyriešiť ľavú polovica tehlovo červená array-- ľavá polovica z nich Ja som teraz vo farbe oranžovej. 

No, mohli by sme skúsiť a tento proces opakovať. Takže sme stále v Uprostred sa snaží vyriešiť ľavá polovica celé pole. Ľavá polovica pole, ja som jednoducho ísť svojvoľne rozhodnúť, že ľavá polovica bude menšia, než v pravej polovici, preto, že sa to stane sa skladá z troch častí. 

A tak budem hovoriť, že Ľavá polovica ľavej polovici Array je len element päť. Five, ktorý je jediný prvok poľa, vieme, ako to vyriešiť. A tak sa päť zoradené. Sme len tak určil. Je to jediný Prvok poľa. 

Preto sme teraz triedi Ľavá polovica ľavého half-- alebo skôr sme triedi Ľavá polovica oranžové. Takže teraz, aby sa ešte kompletné Celkovým array ľavá polovica, musíme radiť pravú polovicu v oranžovej, alebo tejto veci. Ako to urobíme? No, máme dve element poľa. Takže môžeme radiť ľavú polovicu matice, ktorý je dva. Two je jeden element. Takže je to radené v predvolenom nastavení. Potom môžeme radiť pravú polovicu tej časti poľa, ten. To je tak nejako v predvolenom nastavení. 

Toto je teraz prvýkrát sme dosiahli zlúčenie krok. Dokončili sme, hoci Teraz trochu vnorené down-- a to je druh chúlostivé tá vec s rekurzia je, budete potrebovať, aby vaše hlavu o tom, kde sme. Takže sme nejako vľavo polovica oranžovej časti. 

A teraz, sme uprostred triedenie pravá polovica oranžovej časti. A v tomto procese, sme teraz asi byť na kroku spojiť obe polovice k sebe. Keď sa pozrieme na dve polovice matice, vidíme, dva a jeden. Ktorý prvok je menšie? One. 

Potom ktorý element je menšie? No, je to dva alebo nič. Takže je to dva. Takže teraz, len preto, aby znovu rámu kde sme v kontexte, sme triedila Ľavá polovica oranžová a pravá polovica pôvodu. Viem, že som zmenil farby znova, ale to je, kde sme boli. A dôvod, prečo som to urobil je preto, že je tento proces bude ďalej, iterácie dole. Sme radené ľavý polovicu bývalého oranžové a pravá polovica bývalej oranžovej. 

Teraz musíme spojiť tých, dve polovice dohromady taky. To je krok, že sme na. Takže sme do úvahy všetky prvky, ktoré sú teraz zelené, ľavú polovicu pôvodného poľa. A my sme zlúčiť tie pomocou rovnakého procesu sme pre zlúčenie dvoch a pred chvíľou. 

Ľavá polovica, najmenší prvok v ľavej polovici je päť. Najmenší element na pravá polovica je jeden. Ktorý z nich je menšia? One. 

Najmenší element na ľavá polovica je päť. Najmenší element na pravá polovica sú dva. Aký je najmenší? Dva. A potom konečne päť a nič, môžeme povedať, päť. 

OK, takže veľký obrázok, poďme pauzu na sekundu a zistiť, kde sme. Ak by sme začali od samého začiatku, my teraz dokončená celkovej pole len jeden krok zo pseudokódu kódu tu. Máme triedila Ľavá polovica poľa. 

Pripomeňme, že pôvodný Poradie bolo päť, dva, jedna. Tým, že ide v tomto procese a hniezdenia dole a opakovanie, pokračovanie rozbiť problém na menšie a menšie časti, sme teraz dokončili kroku jeden z pseudocode pre celú štartové pole. Máme radené jeho ľavú polovicu. 

Takže teraz poďme tam zmrznúť. A teraz poďme zoradiť právo polovicu pôvodného poľa. A budeme robiť, že prechádza rovnaký iteratívny Proces lámanie veci dole a potom ich zlúči dohromady. 

Takže ľavá polovica červenej, alebo ľavá polovica z pravej polovice originálu pole, budem hovoriť, je tri. Opäť platí, že som tu konzistentné. Ak máte nepárny počet prvkov to, nie je naozaj jedno, či urobíte vľavo jedna menšia alebo právo jedna menšia. 

Dôležité je, že vždy, keď vás narazíte na tento problém v implementácii zlúčenie, musíte byť konzistentné. Buď Vždy musíte urobiť ľavej strane menší alebo vždy potrebné, aby sa pravá strana menšie. Tu som si vybral, aby sa vždy aby sa ľavá strana menšie keď moje pole, alebo my sub-pole, je nepárne veľkosti. 

Tri je jediný prvok, a tak to je triedený. Sme zadlužuje tento predpoklad v celom nášho procesu tak ďaleko. Takže teraz poďme zoradiť právo polovica pravú polovicu, alebo pravá polovica červenej. 

Opäť platí, že musíme rozdeliť tento nadol. To nie je jediný prvok poľa. Nemôžeme vyhlásiť ju za radené. A tak ako prvý, ideme triediť ľavú polovicu. 

Ľavá polovica je jediný prvok, tak je to niečo v predvolenom nastavení. Potom budeme triediť právo polovica, čo je jeden element. Je radené v predvolenom nastavení. A teraz, môžeme spojiť tieto dve dohromady. Štyri je menšie, a potom šiestich je menšia. 

Opäť platí, že to, čo sme urobili v tomto bode? Sme radené ľavý polovica pravú polovicu. Alebo sa vracia k pôvodnému farby, ktoré tam boli, sme radené ľavý polovica mäkšie červené. To bolo pôvodne tmavá tehla červenej a teraz je to mäkšie červená, alebo to bol mäkšie červené. 

A potom sme sa triedi Pravá polovica mäkšie červené. A teraz, no, oni sú zase zelená, len preto, že sme prechádza procesom. A my musíme opakovať to znova a znova. 

Takže teraz sa môžeme spojiť tie, dve polovice dohromady. A to je to, čo robíme tu. Takže čiernou linkou len rozdelil ľavú polovicu a pravá polovica tohto druhu dielu. 

Porovnávame najmenšiu hodnotu na ľavej strane array-- alebo prepáčte, najmenší Hodnota ľavej polovice na najmenšie hodnoty práva polovicou a zistíte, že tri je menšia. A teraz trochu optimalizácia, že jo? Tam je vlastne nič, vľavo na ľavej strane. 

Neexistuje nič, čo zvyšné na ľavej strane, takže môžeme efektívne Len move-- môžeme prehlásiť to ostatné je vlastne triedené a jednoducho ho pripichnúť ďalej, pretože tam nič iný porovnať proti. A my vieme, že na pravej strane z pravej strany sa triedi. 

OK, tak teraz poďme opäť zmrzne a zistiť, kde sme v príbehu. V celkovom poli, čo sme dosiahnuť? My sme vlastne dosiahnuť Teraz kroky jedno a krok dve. Vyriešili sme ľavú polovicu, a sme radené pravú polovicu. 

Takže teraz, všetko, čo zostáva, je pre nás zlúčiť tieto dve polovice dohromady. Takže sme porovnať najnižšou hodnotou prvok každej polovici poľa postupne a pokračovať. Jedným z nich je nižší ako tri, takže jeden ide. 

Dva je nižší ako tri, takže dvoma ide. Tri je menší ako 5, takže tromi ide. Štyri je menší ako 5, takže štyrmi ide. Potom piatich menší ako šesť, a šesť je jediné, čo zostáva. 

Teraz viem, že to bolo veľa krokov. A my sme opustili veľa pamäte v našej brázde. A to je to, čo tie šedé štvorce sú. A to asi pocit, že vzal oveľa dlhšie, než insertion sort, bublina triedenie, alebo výber triedenie. 

Ale v skutočnosti, pretože Mnoho z týchto procesov sa dejú v rovnakom time-- čo je niečo, čo sme to znova, hovorí o tom, kedy hovoríme o rekurzia v budúcnosti video-- tento algoritmus vlastne jasne je zásadne iný ako čokoľvek, sme nevideli ale je tiež významne efektívnejšie. 

Prečo tomu tak je? No, v najhoršom scenár, máme rozdeliť n prvkov up a potom sa zlučujú. Ale keď sme sa rekombinovať je to, čo robíme je v podstate zdvojnásobiť veľkosť menších polí. Máme veľa jedného prvku polí, že sme účinne spojiť do dvoch prvkov poľa. A potom sme sa tým, dve prvok poľa a spojiť ich dohromady do štyri prvok poľa, a tak ďalej, a tak ďalej, a tak ďalej, až kým sme mať jediný n prvok poľa. 

Ale koľko zdvojenie trvá, než sa dostať na n? Spomeňte si na príklad telefónneho zoznamu. Koľkokrát musíme roztrhať telefónny zoznam na polovicu, koľko ďalších časy máme k roztrhnutiu telefónneho zoznamu na polovicu, ak je veľkosť telefónneho zoznamu zdvojnásobil? Je tu len jeden, nie? 

Takže tam je nejaký druh logaritmické prvkom je tu. Ale tiež sme ešte najmenej pozrieť sa na všetky z n prvkov. Takže v najhoršom prípade, merge sort beží v n log n. Musíme sa pozrieť na všetky z n elementy, a musíme kombinovať spolu v protokole n sád krokov. V najlepšom prípade, pole je dokonale zoradené. To je skvelé. Ale na základe algoritmu tu máme, stále musíme rozdeliť a rekombinácie. Aj keď v tomto prípade, rekombinantným je druh neefektívne. To nie je nutné. Ale my stále prejsť celý proces tak ako tak. 

Takže v najlepšom prípade a v najhoršom prípade, Tento algoritmus beží v n log n času. Merge sort je určite niečo ťažšie než ostatné hlavné triedenie algoritmy sme hovorili o CS50, ale je podstatne silnejší. 

A tak ak ste niekedy nájsť príležitosť ju potrebujú alebo ju použiť zoradiť veľký súbor dát, ako sa vaša hlava okolo myšlienky na rekurzia bude naozaj silný. A to bude, aby vaše Programy naozaj oveľa efektívnejšie pomocou merge sort oproti čokoľvek iného. Som Doug Lloyd. To je CS50.