[Zenelejátszási] 

DOUG LLOYD: OK, így egy összevont Rendezés még egy algoritmus hogy tudjuk használni, hogy rendet A tömb elemeit egy. De mint látni fogjuk, hogy van egy Nagyon alapvető különbség a kijelölés sort, buborék rendezése és beillesztés sort hogy teszik igazán elég okos. 

Az alapgondolata merge rendezés rendezni kisebb tömbök és egyesítsük azokat a tömböket együtt, vagy összeolvad them-- így a name-- rendezett sorrendben. Az hogy merge sort csinál ez kiaknázásával a szerszám úgynevezett rekurzív, amely a mi fogunk beszélni hamarosan, de még nem igazán beszéltünk még. 

Itt az alap ötlet mögött merge sort. Rendezés a bal fele a tömb, feltételezve, n értéke 1-nél nagyobb. És mire gondolok, amikor azt mondom, feltételezve, n értéke 1-nél nagyobb, Azt hiszem, abban megegyezhetünk, hogy ha egy tömb csak áll egy elem, ez válogatni. Valójában nem kell hogy bármit hozzá. Mi is csak azt jelenti ki kell válogatni. Ez csak egyetlen elem. 

Tehát a pszeudokódja, újra, A legújabb bal fele a tömb, majd rendezni a jobb oldalán a tömb, majd egyesíteni a két fél együtt. Most már lehet, hogy gondoltam, ez a fajta csak úgy hangzik, mint te teszed le the-- te valójában nem csinál semmit. Azt mondod, hogy rendezze a bal fele, rendezni a jobb fele, de nem mondasz nekem, hogyan csinálod. 

De ne feledjük, hogy amíg Egy tömb egyetlen elem, kijelenthetjük, hogy válogatni. Akkor csak összekapcsolják őket. És ez valóban a alapgondolata merge sort, van lebontani, hogy A tömbök mérete egy. És akkor újjáépíteni onnan. 

Merge sort határozottan egy bonyolult algoritmus. És ez is egy kicsit bonyolult elképzelni. Így remélhetőleg, a vizualizáció, hogy én Van itt segít kövesse végig. És én megpróbálom a legjobb tudásom szerint elbeszélni dolgokat és folytatódik ez egy kicsit lassabban, mint a többinek csak azért, hogy remélhetőleg a fejed az egész ötlet, amin merge sort. 

Tehát akkor ugyanaz a tömb, mint a Más rendezési algoritmus videók ha láttad them-- hat elem tömb. És mi pszeudokódja kódot itt van valami A bal felében rendezni a jobb fele, egyesíti a két fél együtt. Szóval vessünk ennek a nagyon sötét téglavörös tömb és rendezni a bal fele. 

Tehát egyelőre, megyünk hogy figyelmen kívül hagyja a dolgokat a jobb oldalon. Ott van, de nem vagyunk Nem a megfelelő lépésben még. Nem vagyunk sort a jobb felét a tömbben. Mi vagyunk a sort a bal a fele a tömb. És csak a kedvéért Az, hogy egy kicsit többet egyértelmű, így tudok hivatkozni hogy milyen lépéseket vagyunk, Megyek váltani a színes e állítva narancssárga. Most, mi még mindig beszélünk ugyanolyan bal fele az eredeti tömb. De remélem, hogy azáltal, hogy olvassa el a színeket a különböző elemek, ez lesz, hogy ez egy kicsit több világos, hogy mi folyik itt. 

OK, így most van egy három elem tömb. Hogyan rendezni a bal fele ezt tömb, amely még mindig ezt a lépést? Megpróbáljuk rendezni a bal fele a téglavörös array-- a bal fele, amely Már most narancssárga színű. 

Nos, mi is megpróbáljuk ismételje meg ezt a folyamatot újra. Szóval mi még mindig a közepén megpróbálja rendezni A bal fele a teljes tömb. A bal fele tömb, én csak fog hogy pontosan eldönteni, hogy a bal fél kisebb lesz, mint a jobb fél, mert ez történik áll három elemet. 

És így fogom mondani, hogy a bal fele a bal fele a tömb csak az elem öt. Öt, hogy egyetlen elem tömb, tudjuk, hogyan kell rendezni. És így öt rendezve. Mi csak megy, hogy nyilvánítsa. Ez egyetlen elem tömb. 

Így már most válogatni a bal fele a bal half-- vagy inkább, amit válogatni a bal fele a narancs. Tehát most, hogy még a teljes a teljes tömb bal felét, meg kell rendezni a jobb fele A narancs, vagy ez a cucc. Hogyan csináljuk ezt? Nos, van egy két elem tömb. Így tudjuk rendezni a bal fele a tömb, ami két. Két egyetlen eleme. Szóval ez sorolva alapértelmezett. Akkor rendezni a jobb fele az említett rész a tömb, az egyik. Ez a fajta alapból. 

Ez most az első alkalommal elértük merge lépést. Befejeztük, bár mi most egyfajta beágyazott down-- és ez a fajta trükkös dolog rekurzió, meg kell tartani a fej, ​​hogy hol vagyunk. Így már egyfajta bal a fele a narancssárga rész. 

És most, mi vagyunk a közepén válogatás a jobb fele a narancssárga része. És ebben a folyamatban vagyunk Most arról szól, hogy a lépés, egyesíti a két fél együtt. Ha megnézzük a két felét a tömb, azt látjuk, kettő és egy. Melyik elem kisebb? Egy. 

Akkor melyik eleme kisebb? Nos, ez a két, vagy semmit. Tehát ez a két. Tehát most, csak azért, hogy újra a keret hogy hol tartunk a kontextusban, már válogatni a bal fele narancs és a jobb fele az origó. Tudom, hogy már megváltoztatta a színek újra, de ez az, ahol voltunk. És azért tette ezt azért van, mert ez a folyamat fog tartani fog, ismételve le. Már válogatni a bal fele a korábbi narancs és a jobb fele a korábbi narancs. 

Most kell egyesíteni azokat két fél együtt is. Ez a lépés már itt tartunk. Tehát úgy véljük, minden a elemek, amelyek most zöld, A bal fele az eredeti tömb. És mi egyesítése azoknak ugyanazt az eljárást használják tettük egyesülő két és egy csak egy pillanattal ezelőtt. 

A bal felében a legkisebb elemet a bal fele öt. A legkisebb elem a jobb oldalán egy. Azok közül melyik kisebb? Egy. 

A legkisebb elem A bal fele öt. A legkisebb elem a jobb oldalán van kettő. Mi a legkisebb? Kettő. És akkor végül öt és semmit, azt mondhatjuk öt. 

OK, így nagy kép, hadd egy kis szünetet a második és kitalálni, hogy hol vagyunk. Ha abból indultunk ki, A kezdet kezdetén, mi Ezzel befejeződött a a teljes tömb csak egy lépéssel a pszeudokódja kódot itt. Mi már válogatni a bal fele a tömbben. 

Emlékezzünk vissza, hogy az eredeti érdekében öt, kettő, egy. Csak végig kell mennie a folyamatban fészkelő le, és ismétlődő, továbbra is megtörni a problémát le kisebb és kisebb részekre, most már befejezett fokozzák az egyik pszeudokódja az egész kiindulási tömb. Mi már válogatni a bal fele. 

Így most nézzük fagyasztható van. És most nézzük rendezni a jobb a fele az eredeti tömb. És fogunk csinálni, hogy a megy keresztül ugyanazon iteratív folyamata törés dolgokat majd összevonással együtt. 

Így a bal fele piros, vagy a bal fele A jobb fele az eredeti tömb, fogom mondani, három. Ismét én következetes itt. Ha van egy furcsa számú elemet, hogy nem igazán számít, hogy csinál a bal, egy kisebb vagy az igazit kisebb. 

A lényeg, hogy amikor ilyen probléma merül lebonyolítása egy összevont, meg kell, hogy legyen következetes. Vagy mindig kell hogy egy bal oldali kisebb vagy mindig kell, hogy a jobb oldali kisebb. Itt, úgy döntöttem, hogy mindig hogy a bal oldali kisebb amikor a tömb, vagy én tömbbök, a páratlan méretű. 

Három önálló elemként, És ez így van rendezve. Már tőkeáttételes ezt a feltételezést az egész a mi egész folyamat eddig. Így most nézzük rendezni a jobb felét a jobb fél, vagy a jobb fele a piros. 

Ismét meg kell osztani ezt le. Ez nem egy elemet tömb. Nem jelenthetjük ki, hogy válogatni. És így az első, megyünk rendezni a bal felét. 

A bal fele egyetlen elem, így ez a fajta alapból. Aztán megyünk rendezni a jobb fele, amely egyetlen elem. Ez sorolva alapértelmezett. És most, tudjuk egyesíteni a két együttes. Négy kisebb, és majd hat kisebb. 

Ismét mit tettünk ezen a ponton? Már válogatni a bal a fele a jobb felét. Vagy megy vissza az eredeti színek, hogy ott voltak, mi már válogatni a bal a fele a lágyabb vörös. Ez eredetileg egy sötét tégla piros és most ez egy lágyabb piros, vagy ez egy lágyabb vörös. 

És akkor mi már válogatni a jobb felét a lágyabb piros. Most, nos, ők zöld újra, csak mert mi folyamaton megy keresztül. És meg kell ismételni ezt újra és újra. 

Így most már összevonjátok két fél együtt. És ez az, amit mi itt. Így a fekete vonal csak osztva a bal fele és a jobb fele ilyen része. 

Összehasonlítjuk a legkisebb érték a bal oldalon a array-- vagy bocsánat, a legkisebb értéke a bal felét a legkisebb érték a jobb fele és kiderül, hogy a három kisebb. És most egy kicsit az optimalizálás, ugye? Itt tulajdonképpen semmi elhagyta a bal oldalon. 

Nincs semmi fennmaradó a bal oldalon, így tudjuk hatékonyan Csak move-- kijelenthetjük a többi része valójában válogatni és csak csapáson meg tovább, mert nincs semmi mást összehasonlítani. És tudjuk, hogy a jobb oldali A jobb oldalon van rendezve. 

OK, így most nézzük újra lefagyasztani, és kitalálni, hogy hol vagyunk a történetben. A teljes tömb, mit értünk el? Mi már valóban véghez Most lépéseket egy és két lépésben. Mi válogatni a bal fele, és mi válogatni a jobb fele. 

Tehát most, minden marad a számunkra egyesíteni a két fél együtt. Így összevetjük a legalacsonyabb értékű eleme mindkét felét a tömb után, és folytassa. Egy kisebb, mint három, úgy sem megy. 

Két kisebb, mint három, így a két megy. Három kisebb, mint 5, ezért három megy. Négy kisebb, mint 5, így négy megy. Ezután öt kevesebb mint hat, és hat minden marad. 

Most, tudom, hogy volt egy csomó lépést. És mi maradt egy csomó A memória a mi nyomán. És ez az, amit ezek a szürke négyzet. És valószínűleg úgy érezte, mintha, hogy vett egy sokkal hosszabb, mint beillesztés sort, buborék rendezés, illetve kiválasztási sorrend. 

De valójában, mert a sok ilyen folyamatok történnek ugyanabban az time-- ami valami fogunk megint beszélnek, amikor arról beszélünk, rekurzió egy későbbi video-- ez az algoritmus valójában egyértelműen alapvetően más, mint bármi láttuk de az is jelentősen hatékonyabb. 

Miert van az? Nos, a legrosszabb forgatókönyv, van megosztani n elemek akár majd újra össze. De amikor rekombinálódnak őket, mit csinálunk alapvetően megduplázva a méret a kisebb tömbök. Van egy csomó egyik eleme tömbök, hogy hatékonyan egyesíteni a két elem tömbök. És akkor, hogy ezeket a Két elem tömbök és rendezhetjük azokat négy elem tömbök, és így tovább, és így tovább, és így tovább, amíg mi egy N elem tömb. 

De hány megduplázódásának tart eljutni n? Gondolj vissza a telefonkönyv példa. Hányszor kell még, hogy szakadjon A telefonkönyv félbe, még hány alkalommal kell még, hogy szakadjon a telefonkönyv félbe, ha a méret a telefonkönyv megduplázódott? Már csak egy, igaz? 

Szóval van valami logaritmikus eleme van. De azt is mindig van legalább megnézi az összes N elemekkel. Tehát a legrosszabb forgatókönyv esetén, merge sort fut n log n. Meg kell nézni az összes N elemek, és van, hogy összekapcsolják őket együtt log n készlet lépéseket. A legjobb forgatókönyv esetén, A tömb tökéletesen rendezve. Az remek. De az algoritmus alapján mi van itt, még mindig meg kell osztani, és újraegyesítése. Bár ebben az esetben a rekombinálódó a fajta hatástalan. Ez nem szükséges. De még mindig megy keresztül Az egész folyamat egyébként. 

Tehát a legjobb esetben és a legrosszabb esetben, Az algoritmus fut n log n idő. Merge sort mindenképpen egy kicsit trükkösebb mint a másik fő rendező algoritmus beszéltünk CS50 de lényegesen erősebb. 

És így ha valaha is megtalálják alkalma van rá illetve felhasználják rendezni a nagy adathalmaz, egyre fejed köré a gondolat, rekurzió lesz igazán erős. És ez megy, hogy a programok valóban sokkal hatékonyabb az egyesítés rendezési szemben bármi más. Én Doug Lloyd. Ez CS50.