[Přehrávání hudby] 

DOUG LLOYD: OK, takže sloučení sort je dalším algoritmus že můžeme použít vyřešit prvky pole. Ale jak uvidíme, je to dostal velmi zásadní rozdíl z výběr druhu, bublina třídit a insertion sort které dělají to opravdu docela chytrý. 

Základní myšlenkou sloučení třídění je třídit menších polí a pak spojit tyto pole dohromady, nebo sloučit them-- od této doby name-- v seřazeném pořadí. Způsob, jakým merge sort dělá to je využitím nástroje zvané rekurze, což je to, co budeme mluvit o brzy, ale my jsme opravdu mluvil o dosud. 

Zde je základní myšlenka sloučení druhu. Třídit levou polovinu pole, za předpokladu, že n je větší než 1. A co mám na mysli, když říkám za předpokladu, že n je větší než 1, je, Myslím, že se shodneme na tom, že pokud pole pouze se skládá z jednoho prvku, je to třídit. Nemáme skutečně potřebují udělat cokoliv, aby to. Můžeme jen prohlásit, že mají být tříděny. Je to jen jeden prvek. 

Takže pseudocode, opět, je seřadit levé polovině pole, pak třídit pravou polovinu pole, pak sloučit dvě poloviny dohromady. Teď už byste měli být myšlení, je to jen trochu Zní to, jako bys odkládali the-- nejste opravdu dělat nic. Říkáš, že třídit levý polovině, třídit pravou polovinu, ale ty neříkáš me, jak to děláte. 

Ale pamatujte si, že dokud pole je jeden element, můžeme prohlásit, že třídit. Pak se můžeme jen spojit dohromady. A to je vlastně Základní myšlenkou sloučení druhu, je rozebrat to tak, že vaše pole má velikost jednoho. A pak znovu odtamtud. 

Merge sort je určitě komplikovaný algoritmus. A je to také trochu složité představit. Takže doufejme, vizualizace, které jsem zde vám pomůže sledovat spolu. A budu snažit co nejlépe vyprávět věci a pokračovat přes to trochu víc pomaleji než ty ostatní jen doufejme, že si hlavu kolem myšlenek sloučení druhu. 

Takže máme stejné pole jako The další třídění algoritmus videa pokud jste viděli them-- Array šesti prvek. A naše pseudokód kód tady je trochu levá polovina, třídit pravou polovinu, spojit obě poloviny k sobě. Takže pojďme se tento velmi tmavě cihlově červená pole a třídit levou polovinu. 

Takže v současné době, jdeme ignorovat věci na pravé straně. Je to tam, ale my jsme ne na ještě tomto kroku. Nejsme na řadit pravá polovina pole. Jsme na druhu Na levé polovina pole. A jen kvůli z toho, že trochu více jasné, takže mohu odkázat k tomu, co jsme na krok, Budu přepnutí Barva tohoto nastavena na oranžovou. Teď jsme stále mluvil o Totéž levou polovinu původního pole. Ale já doufám, že tím, že je schopen odkazují na barvy různých položek, to bude dělat to o něco více jasné, co se tady děje. 

OK, takže teď máme Tři element pole. Jak můžeme řadit levé polovině tohoto pole, což je stále ještě tento krok? Snažíme se vyřešit levou polovina cihlově červená array-- levá polovina z nich Já jsem teď v barvě oranžové. 

No, mohli bychom zkusit a tento proces opakovat. Takže jsme pořád v Uprostřed se snaží vyřešit levá polovina celé pole. Levá polovina pole, já jsem prostě jít svévolně rozhodnout, že levá polovina bude menší, než v pravé polovině, proto, že se to stane se skládá ze tří částí. 

A tak budu říkat, že Levá polovina levé polovině Array je jen element pět. Five, který je jediný prvek pole, víme, jak to vyřešit. A tak se pět seřazeny. Jsme jen tak určil. Je to jediný element pole. 

Proto jsme nyní třídí Levá polovina levého half-- nebo spíše jsme třídí Levá polovina oranžové. Takže teď, aby se ještě kompletní Celkovým array levá polovina, musíme řadit pravou polovinu v oranžové, nebo této věci. Jak to uděláme? No, máme dvě element pole. Takže můžeme řadit levou polovinu matice, který je dva. Two je jeden element. Takže je to řazeny ve výchozím nastavení. Pak můžeme řadit pravou polovinu té části pole, ten. To je tak nějak ve výchozím nastavení. 

Toto je nyní poprvé jsme dosáhli sloučení krok. Dokončili jsme, ačkoli Nyní trochu vnořené down-- a to je druh choulostivé ta věc s rekurze je, budete potřebovat, aby vaše hlavu o tom, kde jsme. Takže jsme nějak vlevo polovina oranžové části. 

A teď, jsme uprostřed třídění pravá polovina oranžové části. A v tomto procesu, jsme nyní asi být na kroku spojit obě poloviny k sobě. Když se podíváme na dvě poloviny matice, vidíme, dva a jeden. Který prvek je menší? One. 

Pak který element je menší? No, je to dva nebo nic. Takže je to dva. Takže teď, jen proto, aby znovu rámu kde jsme v kontextu, jsme třídila Levá polovina oranžová a pravá polovina původu. Vím, že jsem změnil barvy znovu, ale to je, kde jsme byli. A důvod, proč jsem to udělal je proto, že je tento proces bude dál, iterace dolů. Jsme řazeny levý polovinu bývalého oranžové a pravá polovina bývalé oranžové. 

Teď musíme spojit ty, dvě poloviny dohromady taky. To je krok, že jsme na. Takže jsme v úvahu všechny prvky, které jsou nyní zelené, levou polovinu původního pole. A my jsme sloučit ty pomocí stejného procesu jsme pro sloučení dvou a před chvílí. 

Levá polovina, nejmenší prvek v levé polovině je pět. Nejmenší element na pravá polovina je jeden. Který z nich je menší? One. 

Nejmenší element na levá polovina je pět. Nejmenší element na pravá polovina jsou dva. Jaký je nejmenší? Dva. A pak konečně pět a nic, můžeme říci, pět. 

OK, takže velký obrázek, pojďme pauzu na vteřinu a zjistit, kde jsme. Pokud bychom začali od samého začátku, my nyní dokončena celkové pole jen jeden krok ze pseudokódu kódu zde. Máme třídila Levá polovina pole. 

Připomeňme, že původní Pořadí bylo pět, dva, jedna. Tím, že jde v tomto procesu a hnízdění dolů a opakování, pokračování rozbít problém na menší a menší části, jsme nyní dokončili kroku jeden z pseudocode pro celou startovní pole. Máme řazeny jeho levou polovinu. 

Takže teď pojďme tam zmrznout. A teď pojďme seřadit právo polovinu původního pole. A budeme dělat, že prochází stejný iterativní Proces lámání věci dolů a potom je sloučí dohromady. 

Takže levá polovina červené, nebo levá polovina z pravé poloviny originálu pole, budu říkat, je tři. Opět platí, že jsem tady konzistentní. Máte-li lichý počet prvků to, není opravdu jedno, jestli uděláte vlevo jedna menší nebo právo jedna menší. 

Důležité je, že vždy, když vás narazíte na tento problém v provádění sloučení, musíte být konzistentní. Buď Vždy musíte udělat levé straně menší nebo vždy třeba, aby se na pravé straně menší. Tady jsem si vybral, aby se vždy aby se levá strana menší když moje pole, nebo my sub-pole, je liché velikosti. 

Tři je jediný prvek, a tak to je tříděn. Jsme zadlužuje tento předpoklad v celém našeho procesu tak daleko. Takže teď pojďme seřadit právo polovina pravou polovinu, nebo pravá polovina červené. 

Opět platí, že musíme rozdělit tento dolů. To není jediný prvek pole. Nemůžeme prohlásit ho za řazeny. A tak jako první, jdeme třídit levou polovinu. 

Levá polovina je jediný prvek, tak je to něco ve výchozím nastavení. Pak budeme třídit právo polovina, což je jeden element. Je řazeny ve výchozím nastavení. A nyní, můžeme spojit tyto dvě dohromady. Čtyři je menší, a pak šesti je menší. 

Opět platí, že to, co jsme udělali v tomto bodě? Jsme řazeny levý polovina pravou polovinu. Nebo se vrací k původnímu barvy, které tam byli, jsme řazeny levý polovina měkčí červené. To bylo původně tmavá cihla červené a teď je to měkčí červená, nebo to byl měkčí červené. 

A pak jsme se třídí Pravá polovina měkčí červené. A teď, no, oni jsou zase zelená, jen proto, že jsme prochází procesem. A my musíme opakovat to znovu a znovu. 

Takže teď se můžeme spojit ty, dvě poloviny dohromady. A to je to, co děláme tady. Takže černou linkou jen rozdělil levou polovinu a pravá polovina tohoto druhu dílu. 

Porovnáváme nejmenší hodnotu na levé straně array-- nebo promiňte, nejmenší Hodnota levé poloviny na nejmenší hodnoty práva polovinou a zjistíte, že tři je menší. A teď trochu optimalizace, že jo? Tam je vlastně nic, vlevo na levé straně. 

Neexistuje nic, co zbývající na levé straně, takže můžeme efektivně Jen move-- můžeme prohlásit to ostatní je vlastně tříděny a prostě ho připíchnout dál, protože tam nic jiný porovnat proti. A my víme, že na pravé straně z pravé strany se třídí. 

OK, tak teď pojďme opět zmrzne a zjistit, kde jsme v příběhu. V celkovém poli, co jsme dosáhnout? My jsme vlastně dosáhnout Nyní kroky jedno a krok dvě. Vyřešili jsme levou polovinu, a jsme řazeny pravou polovinu. 

Takže teď, vše, co zůstává, je pro nás sloučit tyto dvě poloviny dohromady. Takže jsme porovnat nejnižší hodnotou prvek každé polovině pole postupně a pokračovat. Jedním z nich je nižší než tři, takže jeden jde. 

Dva je nižší než tři, takže dvěma jde. Tři je menší než 5, takže třemi jde. Čtyři je menší než 5, takže čtyřmi jde. Pak pěti je menší než šest, a šest je jediné, co zůstává. 

Teď vím, že to bylo hodně kroků. A my jsme opustili hodně paměti v naší brázdě. A to je to, co ty šedé čtverce jsou. A to asi pocit, že vzal mnohem déle, než insertion sort, bublina třídění, nebo výběr třídění. 

Ale ve skutečnosti, protože Mnoho z těchto procesů se dějí ve stejném time-- což je něco, co jsme to znovu, mluví o tom, kdy hovoříme o rekurze v budoucnu video-- tento algoritmus vlastně jasně je zásadně jiný než cokoliv, jsme neviděli ale je také významně efektivnější. 

Proč tomu tak je? No, v nejhorším scénář, máme rozdělit n prvků up a pak se slučují. Ale když jsme se rekombinovat je to, co děláme je v podstatě zdvojnásobit velikost menších polí. Máme spoustu jednoho prvku polí, že jsme účinně spojit do dvou prvků pole. A pak jsme se těm, dvě prvek pole a spojit je dohromady do čtyři prvek pole, a tak dále, a tak dále, a tak dále, dokud jsme mít jediný n prvek pole. 

Ale kolik zdvojení trvá, než se dostat na n? Vzpomeňte si na příklad telefonního seznamu. Kolikrát musíme roztrhat telefonní seznam na polovinu, kolik dalších časy máme k roztržení telefonního seznamu na polovinu, pokud je velikost telefonního seznamu zdvojnásobil? Je tu jen jeden, ne? 

Takže tam je nějaký druh logaritmická prvkem je zde. Ale také jsme ještě nejméně podívat se na všechny z n prvků. Takže v nejhorším případě, merge sort běží v n log n. Musíme se podívat na všechny z n elementy, a musíme kombinovat spolu v protokolu n sad kroků. V nejlepším případě, pole je dokonale seřazeny. To je skvělé. Ale na základě algoritmu tady máme, stále musíme rozdělit a rekombinace. I když v tomto případě, rekombinantním je druh neefektivní. To není nutné. Ale my pořád projít celý proces tak jako tak. 

Takže v nejlepším případě a v nejhorším případě, Tento algoritmus běží v n log n času. Merge sort je určitě něco obtížnější než ostatní hlavní třídění algoritmy jsme mluvili o CS50, ale je podstatně silnější. 

A tak pokud jste někdy najít příležitost ji potřebují nebo ji použít seřadit velký soubor dat, jak se vaše hlava kolem myšlenky na rekurze bude opravdu silný. A to bude, aby vaše Programy opravdu mnohem efektivnější pomocí merge sort oproti cokoliv jiného. Jsem Doug Lloyd. To je CS50.