[Predvaja glasba] 

Doug LLOYD: OK, tako da se združita nekako je še en algoritem da bomo lahko uporabite rešiti elementi matrike. Toda, kot bomo videli, je to dobil zelo bistvena razlika od izbor sort, bubble razvrščanje in vstavljanje nekako zaradi katerih je v resnici zelo pameten. 

Osnovna ideja spajanje Razvrsti je razvrstiti manjše nize in nato združite tiste nize skupaj ali združijo them-- zato name-- v urejenem zaporedju. Tako, da zlivanjem ne to je s povečanjem orodje imenovano rekurzija, ki je kaj bomo govorili o tem kmalu, vendar nismo zares govorila še. 

Tukaj je osnovna ideja zlivanjem. Razvrstiti levo polovico matrike, ob predpostavki, n je večji od 1. In kaj mislim, ko rečem predpostavki n večji od 1, je, Mislim, da se lahko strinjamo, da če niz Samo sestoji iz enega samega elementa, to je urejeno. Mi dejansko ne potrebujemo storiti ničesar, da bi to. Mi lahko samo razglaša bodo razporejene. To je samo en element. 

Torej psevdokoda, še enkrat, je razvrstiti levi polovici matrike, nato razvrstite desno polovico matrika, nato združite obe polovici skupaj. Zdaj pa že boste morda misleč, da nekako le Sliši se, kot da ste zavlačevanja the-- ste dejansko ne počne ničesar. Praviš razvrstiti levo pol, razvrstiti desno polovico, vendar nisi povedal me, kako to počnete. 

Ampak ne pozabite, da dokler matrika je en sam element, bomo lahko razglasila razporejene. Potem bomo lahko samo jih združiti skupaj. In to je pravzaprav Temeljna ideja zlivanjem, je, da razgradi, tako da vaši nizi so velikosti enega. In potem ko ste obnovili od tam. 

Zlivanjem je definitivno zapleten algoritem. In to je tudi malo zapleten vizualizirati. Torej upajmo, vizualizacija, ki sem imajo tu vam bo pomagal sledite skupaj. In bom poskusil moje najbolje, da pripovedujejo stvari in nadaljuje skozi to malo bolj počasneje od ostalih, samo, da upajmo, da bi dobili svojo glavo okoli ideje zlivanjem. 

Torej imamo isto vrsto kot drugi sortiranje algoritem videos če ste videli them-- Niz šest element. In naša psevdokoda koda tukaj je nekako levo polovico, razvrstiti desno polovico, združiti obe polovici skupaj. Tako da je to zelo temno opečnato rdeča Niz in razvrstiti levo polovico tega. 

Torej za zdaj, gremo prezreti stvari na desni strani. To je tam, vendar smo ne pa v tej fazi še ni. Nismo na Razvrščanje Desna polovica matriki. Mi smo na vrsto po levi polovica matriki. In samo zavoljo , da so malo bolj Jasno, da sem se lahko nanašajo s tem, kar korak smo na, Jaz grem za preklop Barva tega niza v oranžno. Zdaj smo še vedno govorimo o Enako levo polovico prvotnega niza. Vendar sem upal, da ga bi mogli nanašajo na barve različnih predmetov, da bomo, da je nekoliko bolj jasno, kaj se dogaja tukaj. 

OK, tako da zdaj imamo tri element matrike. Kako bomo levo polovico te vrste matrika, ki je še vedno ta korak? Poskušamo rešiti levo polovica opečnato rdeča array-- leva polovica katerih Sem zdaj obarvana oranžno. 

No, lahko bi poskusila Ta postopek ponovite. Torej smo še vedno v Sredi poskuša rešiti levo polovico celotnega niza. Leva polovica matrika, sem le, da bo samovoljno odloči, da leva polovica bo manjši kot desni polovici, ker se to zgodi sestavljen iz treh elementov. 

In tako bom rekel, da je leva polovica levi polovici matrike je le element pet. Pet, pri čemer je en sam element matrika, vemo, kako ga rešiti. In tako pet je razvrščen. Mi smo le, da bo razglasila, da je. To je en sam element matrike. 

Tako smo zdaj razporejene leva polovica kazenski half-- ali bolje, smo razporejene leva polovica oranžno. Zdaj, da bi se vedno nahaja leva polovica splošnim Array je, moramo razvrstiti desno polovico od oranžne, ali te stvari. Kako to storimo? No, imamo niz dveh elementov. Tako bomo lahko z levo polovico razvrstiti matrike, ki je dva. Dva enojna element. Torej je to urejeno privzeto. Potem bomo lahko z desno polovico razvrstiti tega dela polja, v eno. To je nekako privzeto. 

To je sedaj prvič smo dosegli spajanje korak. Zaključili smo, čeprav smo zdaj nekako ugnezdena down-- in to je neke vrste rafiniran stvar z rekurzije je, morate, da bo vaš glavo o tem, kje smo. Zato smo nekako v levo polovica oranžno odseka. 

In zdaj, smo sredi sortiranje desno polovico oranžnega odseka. In v tem procesu, smo Zdaj bo kmalu na koraku združiti obe polovici skupaj. Ko gledamo na dveh polovic array, vidimo dva in enega. Kateri element je manjša? Ena. 

Potem kateri element je manjša? No, to je dva ali nič. Torej, to je dva. Torej sedaj, samo da spet okvir kjer smo v okviru smo razporejene leva polovica oranžne in desno polovico izvora. Vem, da sem spremenila barve spet, ampak da je, kjer smo bili. In razlog, zakaj sem to storil je zato, ker je ta proces dogaja, da se dogaja, ponavljanjem dol. Mi smo razporejene levo polovica nekdanjega oranžne in desno polovico nekdanjega oranžno. 

Zdaj moramo združiti tiste, Polovici skupaj preveč. To je korak, da smo na. Zato menimo, da vse elemente, ki so zdaj zelena, levo polovico prvotnega niza. In smo združiti tiste, po istem postopku smo naredili za združitev dveh in eno samo trenutek nazaj. 

Leva polovica, najmanjša element na levi polovici je pet. Najmanjši element na desna polovica je ena. Kateri od teh je manjši? Ena. 

Najmanjši element na leva polovica je pet. Najmanjši element na desna polovica je dva. Kakšna je najmanjša? Dva. In potem na koncu pet in nič, lahko rečemo, pet. 

OK, tako velika slika, kaj je odmor za sekundo in ugotoviti, kje smo. Če smo začeli z samega začetka smo so zdaj končana za celotna matrika samo en korak kode psevdokoda tukaj. Smo razporejene leva polovica matriki. 

Spomnimo se, da je bila prvotna Da bi imel pet, dve, ena. Skozi ta proces in gnezdijo navzdol in ponavljanje, nadaljuje, da bi prekinil problem v manjše in manjše dele, smo zdaj končana korak eden od psevdokoda za celotno začetno zaporedje. Imamo razporejene svojo levo polovico. 

Torej, zdaj pa zamrzne tam. In sedaj dajmo razvrstiti pravico polovico prvotnega niza. In bomo storiti, da jih gredo skozi isto iterativni Proces breaking stvari navzdol in jih nato združujejo. 

Torej leva polovica rdeče ali levo polovico desne polovice originalnega matrika, bom rekel, je tri. Spet sem biti skladna tukaj. Če imate neparno število elementov tako, sploh ni pomembno, ali naredite levo ena manjša ali desno ena manjša. 

Pomembno je, da vsakič, ko vas naleteli na to težavo pri vodenju Združitev, morate biti dosledni. Ali boste vedno morali narediti levo stran manjša ali vedno treba narediti na desni strani manjši. Tukaj sem izbral, da vedno da leva stran manjša ko je moj matrika, ali moj sub-matrika, je liho velikosti. 

Tri je posamezen element, in se tako razporejene. Mi smo vzvodom to domnevo vsej naši celotnem procesu doslej. Torej, zdaj pa si razvrstiti pravico polovica desni polovici, ali desno polovico rdeče. 

Spet moramo razdeliti to navzdol. To ni en sam element matrika. Ne moremo razglaša razporejene. In tako najprej gremo razvrstiti levo polovico. 

Leva polovica je en sam element, tako da je nekako privzeto. Potem bomo razvrstiti pravico pol, ki je en sam element. To je urejeno privzeto. In zdaj, moremo združiti tiste dve skupaj. Štiri je manjše, in nato šest manjši. 

Še enkrat, kaj smo naredili na tem mestu? Mi smo razporejene levo polovica desni polovici. Ali gre nazaj v izvirniku Barve, ki so bili tam, smo razporejene levo polovica mehkejšega rdečega. To je bil sprva temno opeke rdeče in zdaj je mehkejša rdeča, ali pa je mehkejša rdeče. 

In potem smo razporejene Desna polovica mehkejšega rdečega. Sedaj, dobro, oni zeleni spet, samo ker gremo skozi proces. In moramo ponoviti to znova in znova. 

Torej, zdaj smo lahko združi tiste, Polovici skupaj. In to je tisto, kar počnemo tukaj. Torej črno črto tik razdeljen levo polovico in desno polovico te vrste dela. 

Primerjamo najmanjšo vrednost na levi strani array-- ali oprostite, najmanjši Vrednost levi polovici do najmanjše vrednosti pravice pol, in ugotovili, da je tri manjše. In zdaj malo optimizacije, kajne? Tam je pravzaprav nič levo na levi strani. 

Nič ni preostalo na levi strani, tako da bomo lahko učinkovito Samo move-- moremo razglasiti preostanek pa je pravzaprav razporejene in šele tack no, saj ni nič drugega, da se primerjajo. In vemo, da je desna stran na desni strani je razvrščen. 

OK, zdaj pa zamrzne znova in ugotovimo, kje smo v zgodbi. V celotni niz, Kaj smo dosegli? Mi smo dejansko dosegli Sedaj koraka ena in dva korak. Razporejene smo levo polovico, in smo razporejene desni polovici. 

Torej sedaj, vse, kar ostane, je za nas za združitev teh dveh polovic skupaj. Tako smo primerjali najnižja vrednoti element vsaki polovici matrike v zameno in nadaljujte. Eden od njih je manj kot tri, tako da nekdo gre. 

Dva manjša od tri, tako da dva gre. Tri je manj kot 5, tako da tri gre. Štiri je manj kot 5, tako da štiri gre. Potem je pet manj kot šest, in šest je vse, kar ostane. 

Zdaj vem, da je bilo veliko korakov. In smo pustili veliko spomina v našem zgledu. In to je tisto, kar ti sivi kvadrati so. In verjetno se počutil, kot da je vzel Veliko več od vstavitve vrste, mehurček razvrščanje, ali izbira vrste. 

Ampak v resnici, ker Veliko teh procesov se dogaja na isti time-- kar je nekaj, kar bomo spet govori o tem, ko govorimo o rekurzija v prihodnosti video-- Ta algoritem dejansko jasno je bistveno drugačna od vsega, smo videli pred vendar je tudi bistveno bolj učinkovito. 

Zakaj je tako? No, v najslabšem scenarij, imamo razdeliti n elementov up in jih nato rekombinacije. Toda, ko smo rekombinacije jim, kaj delamo je v bistvu podvojitev velikost manjših polj. Imamo kup enega elementa nizi da učinkovito združiti v dveh matrikah elementov. In potem smo se tisti, dve nizi elementov in jih združite v štirje nizi elementov, in tako naprej, in tako naprej, in tako naprej, dokler ne bomo ima en sam n element matriko. 

Toda koliko podvajanjih je potrebno, da pridete do n? Pomislite na primer telefonski imenik. Kolikokrat moramo trgati imenika na pol, koliko več krat imamo trgati imenika na pol, če velikost imenika podvojila? Obstaja samo ena, kajne? 

Torej je neke vrste logaritemsko element tukaj. Vendar imamo tudi še vsaj poglej vse n elementov. Torej, v najslabšem primeru, zlivanjem teče v n log n. Moramo gledati vse n elementov, in jih moramo kombinirati skupaj v dnevniku n sklopov korakov. V najboljšem primeru, array je popolnoma urejeno. To je super. Temveč temelji na algoritmu imamo tod bomo še vedno morali razdeliti in rekombinacije. Čeprav je v tem primeru rekombinacija je nekako neučinkovita. Ni potrebno. Vendar smo še vedno iti skozi celoten proces anyway. 

Torej v najboljšem primeru in v najslabšem primeru, Ta algoritem teče v n log n časa. Zlivanjem je definitivno malo težje od drugih glavnih algoritmov za razvrščanje smo se pogovarjali o CS50, vendar je bistveno močnejši. 

In tako, če boste kdaj našli priložnost, da jo potrebujejo ali jo uporabite za razvrščate Velik nabor podatkov, pridobivanje tvoja glava okoli idejo rekurzije se bo res močna. In to se dogaja, da se vaš programi res veliko bolj učinkovito uporabo zlivanjem versus karkoli drugega. Sem Doug Lloyd. To je CS50.