[MUSIC JOC] 

DOUG LLOYD: OK, deci o îmbinare fel este încă un alt algoritm pe care le putem folosi pentru a rezolva elementele unei matrice. Dar, așa cum vom vedea, are o diferență foarte fundamentală de la selecție fel, cu bule sortare, și sortare prin inserție care fac într-adevăr destul de inteligent. 

Ideea de bază merge fel este de a sorta tablouri mai mici și apoi combină aceste tablouri împreună, sau fuziona them-- prin urmare, name-- în ordine sortată. Modul în care merge sort face acest lucru este prin folosirea un instrument numit recursivitate, care este ceea ce vom vorbi despre curând, dar nu am cu adevărat vorbit despre încă. 

Iată ideea de bază din spatele merge sort. Sorta jumătatea stângă a matrice, presupunând n este mai mare decât 1. Și ce vreau să spun când spun presupunând n este mai mare decât 1 este, Cred că putem fi de acord că, dacă o serie doar constă dintr-un singur element, e sortate. Noi de fapt nu au nevoie de a face ceva la ea. Putem declara doar să fie sortate. E doar un singur element. 

Deci Pseudocodul, din nou, este sorta jumătatea stângă a matrice, apoi sorta jumătatea dreaptă matrice, apoi îmbinați cele două jumătăți împreună. Acum, s-ar putea să fie deja gândire, un fel de doar Sună ca și cum ai pune pe the-- nu faci de fapt nimic. Vrei să spui că sorta stânga jumătate, sorta jumătatea din dreapta, dar nu spui mi cum o faci. 

Dar amintiți-vă că, atâta timp cât o matrice este un singur element, putem declare sortate. Atunci putem combina doar le împreună. Și asta e de fapt Ideea fundamentală din spatele merge sort, este să-l rupe în jos, astfel încât tablouri tale sunt de dimensiuni unul. Și apoi reconstrui de acolo. 

Merge fel este cu siguranta un algoritm complicat. Și este, de asemenea, un pic complicat de a vizualiza. Deci, sperăm, vizualizarea pe care am avem aici va ajuta să urmați de-a lungul. Și voi încerca meu cel mai bun pentru a relata lucrurile și să treacă prin acest lucru un pic mai mult încet decât celelalte doar pentru a obține, sperăm cap în jurul valorii de ideile din spatele merge sort. 

Deci avem aceeași matrice ca alte sortare videoclipuri algoritm dacă ați văzut them-- o gamă de șase element de. Și codul pseudocod aici este un fel jumătatea din stânga, sorta jumătatea din dreapta, fuziona cele două jumătăți împreună. Așa că haideți să ia acest rosu foarte inchis cărămidă matrice și sorta jumătatea stângă a acestuia. 

Deci, pentru moment, vom să ignore lucrurile pe dreapta. E acolo, dar suntem nu la acest pas încă. Nu suntem la fel jumătate din dreapta a matrice. Suntem la fel stânga jumătate din matrice. Și doar de dragul de a fi un pic mai mult clar, așa că am putea referi la ceea ce pas suntem pe, Mă duc pentru a comuta Culoarea de acest set la portocaliu. Acum, suntem încă vorbesc despre același jumătatea stângă a șirului original. Dar eu sunt în speranța că prin posibilitatea de a se referă la culorile diverse articole, acesta va face un pic mai mult clar ce se întâmplă aici. 

OK, asa ca acum avem un trei matrice elemente. Cum putem sorta jumătatea stângă a acestei matrice, care este încă acest pas? Încercăm să sorta stânga jumătate din array-- roșu de cărămidă din care jumătatea stângă Acum am colorat portocaliu. 

Ei bine, am putea încerca și repetați din nou acest proces. Deci suntem încă în mijloc de a încerca de a sorta jumătatea stângă a tabloului complet. Jumătatea stângă a matrice, Mă duc pentru a decide în mod arbitrar că jumătatea stângă va fi mai mică decât jumătatea din dreapta, deoarece acest lucru se întâmplă pentru a constau din trei elemente. 

Și așa am de gând să spun că jumătate din stânga a jumătatea stângă matrice este doar elementul cinci. Cinci, fiind un singur element matrice, știm cum să-l rezolve. Și astfel cinci este sortată. Noi doar o să declare că. Este un singur element de matrice. 

Deci ne-am sortat acum jumătatea stângă a half-- stânga sau mai degrabă, am sortează jumătatea stângă a Orange. Deci, acum, în scopul de a încă complet jumătate stânga matrice generală, a avem nevoie pentru a sorta jumătatea din dreapta de portocaliu, sau chestia asta. Cum facem asta? Ei bine, avem o gamă de două elemente. Deci, putem sorta jumătatea stângă de matrice, care este de două. Doi este un singur element. Deci, este sortate în mod implicit. Apoi, putem sorta jumătatea din dreapta acelei porțiuni din matrice, cea. Asta e un fel de mod implicit. 

Aceasta este acum pentru prima dată am ajuns un pas merge. Am finalizat, deși suntem acum un fel de imbricate down-- și asta e un fel de complicat lucru cu recursivitate este, aveți nevoie pentru a vă menține cap despre unde suntem. Deci, ne-am un fel de stânga jumătate din porțiunea portocaliu. 

Și acum, suntem în mijlocul de sortare jumătatea dreaptă a porțiunii portocaliu. Și în acest proces, suntem acum pe cale de a fi pe treapta, fuziona cele două jumătăți împreună. Când ne uităm la cele două jumătăți de matrice, vedem două și unul. Care element este mai mic? Unul. 

Atunci care elementul este mai mic? Ei bine, e două sau nimic. Deci e doi. Deci, acum, doar pentru a încadra din nou unde suntem în context, am sortează jumătatea stângă a portocaliu și jumătatea dreaptă a originii. Știu că am schimbat culorile din nou, dar asta e în cazul în care am fost. Și motivul pentru care am făcut acest lucru se datorează faptului că acest proces este O să continui, iterarea jos. Am sortat stânga jumătate din fosta portocaliu și jumătatea dreaptă a fostului portocaliu. 

Acum, avem nevoie pentru a fuziona cele două jumătăți împreună prea. Acesta este pasul suntem pe. Deci, avem în vedere cele de mai elemente care sunt acum verde, jumătatea stângă a șirului original. Și am merge pe cei utilizând același proces am facut-o pentru fuzionarea două și acum o doar un moment. 

Jumătatea din stânga, cel mai mic element de pe jumătatea stângă este de cinci. Cel mai mic element constitutiv al jumătatea dreaptă este una. Care dintre cei este mai mic? Unul. 

Cel mai mic element constitutiv al jumătatea stângă este de cinci. Cel mai mic element constitutiv al jumătatea dreaptă este de două. Care este cel mai mic? Două. Și apoi în cele din urmă de cinci și nimic, putem spune de cinci. 

OK, imagine atât de mare, să ia o pauză pentru un al doilea și dau seama unde suntem. Dacă am pornit de la Încă de la început, ne-am au încheiat acum pentru matrice de ansamblu doar un pas de cod pseudocod aici. Am sortează jumătatea stângă a tabloului. 

Amintiți-vă că originalul comanda a fost cinci, doi, unu. Trecând prin acest proces și cuiburi în jos și se repetă, continuând să rupă problema jos în bucăți mai mici și mai mici, am finalizat acum pas unul din pseudocod pentru întreaga matrice de pornire. Am sortat jumătate stângă. 

Deci, acum hai să înghețe acolo. Și acum să sorteze dreapta jumătate din matrice originale. Și am de gând să fac asta de trece prin același iterativ proces de rupere jos lucruri și apoi fuzionarea lor împreună. 

Deci, jumătatea stângă a roșu, sau jumătatea stângă din jumătatea dreaptă a originalului matrice, am de gând să spun este de trei. Din nou, am fi consecvent aici. Dacă aveți un ciudat Numărul de elemente ea, Nu contează cu adevărat dacă faci cel mai mic din stânga sau cel din dreapta mai mici. 

Ceea ce contează este că ori de câte ori întâlniți această problemă în desfășurarea a merge, trebuie să fie în concordanță. Ori nevoie întotdeauna să face o partea stângă mai mic sau întotdeauna nevoie pentru a face partea dreapta mai mici. Aici, am ales să întotdeauna face partea din stânga mic când matrice meu, sau meu sub-matrice, este de o dimensiune ciudat. 

Trei este un singur element, Și așa este sortate. Am indatorare ca ipoteză de-a lungul întregii noastre proces de până acum. Deci, acum să sorteze dreapta jumătate din jumătatea din dreapta, sau jumătatea dreaptă a roșu. 

Din nou, avem nevoie de a împărți această jos. Acesta nu este un singur element de matrice. Nu putem declare sortate. Și astfel în primul rând, vom pentru a sorta jumătatea stângă. 

Jumătatea din stânga este un singur element, așa că este un fel de mod implicit. Apoi vom sorta dreapta jumătate, care este un singur element. Este sortate în mod implicit. Si acum, putem merge pe cei doi împreună. Patru este mai mic, și apoi din șase este mai mică. 

Din nou, ceea ce am făcut în acest moment? Am sortat stânga jumătate din jumătatea din dreapta. Sau de a merge inapoi la original culori care au fost acolo, am sortat stânga jumătate din roșu moale. Aceasta a fost inițial o cărămidă întuneric roșu și acum e un roșu mai moale, sau a fost un roșu mai moale. 

Și apoi am sortează jumătatea dreaptă a roșu moale. Acum, ei bine, sunt verde din nou, doar pentru că mergem printr-un proces. Și noi trebuie să repete acest peste si peste. 

Deci, acum putem merge pe cei două jumătăți împreună. Și asta e ceea ce facem noi aici. Deci linia neagră doar împărțit jumătatea stângă și jumătatea dreaptă a acestei părți fel. 

Vom compara mai mică valoare pe partea stângă a array-- sau scuză-mă, cel mai mic Valoarea de jumătatea stângă la cea mai mică valoare a dreptului jumătate și pentru a găsi că trei este mai mică. Și acum un pic de o optimizare, nu? Nu e de fapt nimic stânga pe partea stângă. 

Nu e nimic rămas pe partea stanga, astfel încât să putem eficient doar move-- putem declara restul de acesta este de fapt sortati si doar tac pe, pentru că nu e nimic altceva pentru a compara împotriva. Și știm că pe partea dreapta din partea dreapta este sortat. 

OK, asa ca acum să înghețe din nou și dau seama unde suntem în poveste. În matrice de ansamblu, ceea ce am realizat? Am realiza de fapt acum pașii unu și pasul doi. Am sortat jumătatea stângă, și am sortat jumătatea din dreapta. 

Deci, acum, tot ce rămâne este pentru noi să fuzioneze cele două jumătăți împreună. Așa că am compara cel mai mic apreciate Element de fiecare jumătate de matrice la rândul său, și se procedează. Una dintre ele este mai mic de trei, așa se duce. 

Două este mai mică de trei, așa doua trece. Trei este mai mică de 5, așa de trei merge. Patru este mai mică de 5, așa cu patru trece. Apoi cinci este mai mic de șase, și șase este tot ce rămâne. 

Acum, știu că a fost o mulțime de pași. Și am lăsat o mulțime de memorie în urma noastră. Și asta e ceea ce aceste pătrate gri sunt. Și, probabil, m-am simtit ca un, care a avut mult mai mult decât sortare prin inserție, cu bule un fel, sau de selecție fel. 

Dar, de fapt, pentru că o mulțime de aceste procese se întâmplă în același time-- care este ceva ce vom, din nou, vorbesc despre atunci când vorbim despre recursivitate într-un viitor video-- acest algoritm de fapt în mod clar este fundamental diferit de orice am văzut înainte dar este, de asemenea, semnificativ mai eficient. 

De ce este asta? Ei bine, în cel mai rău scenariu, avem a împărți n elemente sus și apoi recombina le. Dar când am recombina ei, ce facem este, în principiu dublarea mărimea matrice mici. Avem o grămadă de un element tablouri pe care le în mod eficient combina în două tablouri de elemente. Și apoi vom lua cele două tablouri de elemente și să le combine împreună în patru tablouri elemente, și așa mai departe, și așa mai departe, și așa mai departe, până când vom au un singur tablou n elemente. 

Dar cum de multe dublări nu-l ia pentru a ajunge la n? Gandeste-te la exemplul cartea de telefon. De câte ori avem de a rupe cartea de telefon în jumătate, câte ori avem de a rupe cartea de telefon în jumătate, în cazul în care dimensiunea de cartea de telefon dublat? Există doar un singur, nu? 

Deci, există un fel de Element logaritmică aici. Dar noi, de asemenea, mai avem cel puțin uita-te la toate n elemente. Deci, în cel mai rău caz, merge sort rulează în n log n. Trebuie să se uite la toate n elemente, și trebuie să le combine împreună în jurnalul n seturi de trepte. În cel mai bun caz, matrice sunt sortate perfect. Grozav. Dar, pe baza algoritmului avem aici, mai avem de a împărți și recombina. Deși în acest caz, recombinarea este un fel de ineficient. Nu este necesar. Dar noi încă trece prin întregul proces, oricum. 

Deci, în cel mai bun caz și în cel mai rău caz, acest algoritm se execută în n log n timp. Merge fel este cu siguranta un pic mai complicată decât celelalte algoritmii principali de sortare am vorbit despre CS50, dar este mult mai puternic. 

Și așa că, dacă găsi vreodată ocazia să nevoie de ea sau să-l folosească pentru a sorta o set mare de date, obtinerea capul în jurul ideii de recursivitate va fi foarte puternic. Și o să vă face programe într-adevăr mult mai eficient folosind merge sort fata de orice altceva. Sunt Doug Lloyd. Acest lucru este CS50.