[MUZIKO Ludante] 

DOUG LLOYD: Bone, do a merge varo estas ankoraŭ alia algoritmo ke ni povas uzi por ordigi la elementoj de tabelo. Sed kiel ni vidos, ĝi estas alvenis al tre fundamenta diferenco el selektado varon, bobelo speco, kaj inserción varo kiuj faras ĝin vere tre lertaj. 

La baza ideo malantaŭ merge varo estas ordigi malgrandaj tabeloj kaj tiam kombini tiujn tabeloj kune, aŭ kunfandi them-- tie la name-- en ordo ordo. La maniero ke kunfandi speco faras ĉi estas por utiligante ilo nomata rekursio, kio estas kio ni tuj parolos pri baldaŭ, sed ni ne vere parolis ankoraŭ. 

Jen la baza ideo malantaŭ merge varon. Ordigi la maldekstra duono de la tabelo, supozante n pli granda ol 1. Kaj kion mi volas diri kiam mi diras supozante n pli granda ol 1 estas, Mi kredas ke ni povas konsenti ke se tabelo nur konsistas de sola elemento, ĝi estas ordo. Ni ne vere bezonas fari ion al ŝi. Ni povas nur diveni esti ordo. Estas nur unu sola ero. 

Do la _pseudocode_, denove, estas ordigi la maldekstra duono de la tabelo, tiam ordigi la dekstra duono de la tabelo, tiam kunfandi la du duonojn kune. Nun, jam vi povus esti pensante, ĝi speco de simple sonas vi demeto the-- vi fakte ne fari ion. Vi diras ordigi la maldekstra duono, ordigi la dekstra duono, sed vi ne rakontanta mi kiel vi faras ĝin. 

Sed memoru, ke dum tabelo estas ununura ero, ni povas diveni ordo. Tiam ni povas nur kombini ilin kune. Kaj tio estas vere la fundamenta ideo malantaŭ merge varo, estas rompi ĝin malsupren tiel ke via arrays estas de amplekso unu. Kaj tiam vi rekonstruas de tie. 

Kunfandi varo estas definitive komplika algoritmo. Kaj ĝi estas ankaŭ iom komplika visualizar. Do espereble, la visualización ke mi havas tie helpos vin sekvi kune. Kaj mi provos mian plejeblon por rakonti aferojn kaj procedi tra tiu iom pli malrapide ol la alia ones nur espereble ricevos vian kapon ĉirkaŭ la ideoj malantaŭ merge varon. 

Do ni havas la sama tabelo kiel la aliaj ordiga algoritmo filmetoj se vi vidis them-- ses elemento tabelo. Kaj nia _pseudocode_ kodo tie estas ia la maldekstra duono, ordigi la dekstra duono, kunfandi la du duonojn kune. Do ni prenu tiun tre malhela briko ruĝa tabelo kaj ordigi la maldekstra duono. 

Do provizore, ni tuj ignori la havajxoj dekstre. Ĝi estas tie, sed ni estas ne en tiu paŝo ankoraŭ. Ni ne estas en la speco dekstra duono de la tabelo. Ni estas ĉe ia maldekstre duono de la tabelo. Kaj ĝuste pro esti iom pli klara, do mi povas referi al kio paŝo ni estas sur, Mi tuj ŝanĝos la koloro de ĉi tiu aro al oranĝo. Nun, ni ankoraŭ parolas pri la sama maldekstra duono de la originala tabelo. Sed mi esperas, ke por povi rilati al la koloroj de diversaj artikoloj, gxi devos fari ĝin iom pli malbari kion okazas tie. 

Bone, do nun ni havas tri elemento tabelo. Kiel ni ordigi la maldekstra duono de tiu tabelo, kiu estas ankoraŭ ĉi paŝon? Ni provas ordigi la maldekstra duono de la briko ruĝa tabelo la maldekstra duono de kiu Mi nun kolorita oranĝa. 

Nu, ni povus provi kaj Ripeti ĉi procezo denove. Do ni estas ankoraŭ en la mezo de provi ordigi la maldekstra duono de la plena tabelo. La maldekstra duono de la tabelo, mi simple tuj arbitre decidi ke la maldekstra duono estos pli malgranda ol la dekstra duono, ĉar ĉi tio okazas al konsisti el tri elementoj. 

Kaj tiel mi tuj diru, ke la maldekstra duono de la maldekstra duono de la tabelo Estas ĝuste la elemento kvin. Kvin, estante sola elemento tabelo, ni scias kiel ordigi ĝin. Kaj do kvin estas ordo. Ni nur tuj deklari tion. Ĝi estas ununura elemento tabelo. 

Do ni nun ordo la maldekstra duono de la maldekstra half-- aŭ pli ĝuste, ni ordo la maldekstra duono de la oranĝo. Do nun, por ankoraŭ kompleta la totala tabelo la maldekstra duono, ni devas ordigi la dekstra duono de la oranĝo, aŭ tiun materialon. Kiel ni faru tion? Nu, ni havas du elemento tabelo. Do ni povas ordigi la maldekstra duono de la tabelo, kiu estas du. Du estas ununura elemento. Do ĝi estas ordo defaŭlte. Tiam ni povas ordigi la dekstra duono de tiu parto de la tabelo, la unu. Tio estas speco de defaŭlte. 

Jen nun la unuan fojon ni atingis merge paŝo. Ni kompletigis, kvankam ni nun speco de nestitaj down-- kaj tio estas ia la delikata afero kun rekursio estas, vi bezonas konservi vian kapo pri kie ni estas. Do ni ia maldekstre duono de la oranĝo porcion. 

Nun ni estas en la mezo de ordiga la dekstra duono de la oranĝo porcion. En tiu procezo, ni estas nun baldaux estos sur la ŝtupo, kunfandi la du duonojn kune. Kiam ni rigardas la du duonoj de la tabelo, ni vidas du unu. Kiu elemento estas malgranda? Unu. 

Tiam kiun elemento estas malgranda? Nu, estas du aŭ nenio. Do estas du. Do nun, nur por denove enmarcar kie ni estas en kunteksto, ni ordo la maldekstra duono de la oranĝo kaj la dekstran duonon de la origino. Mi scias ke mi ŝanĝis la kolorojn denove, sed tio estas kie ni estis. Kaj la kialo mi faris tion estas ĉar tiu procezo estas tuj plu iri, ripetanta suben. Ni ordo maldekstren duono de la iama oranĝo kaj la dekstran duonon de la iama oranĝo. 

Nun, ni bezonas kunfandi tiujn du duonojn kune tro. Tio estas la paŝo ni estas sur. Do ni konsideras ĉiujn elementoj, kiuj estas nun verda, la maldekstra duono de la originala tabelo. Kaj ni kunfandi tiujn uzante la saman procezon ni faris por kunfalado du kaj unu nur antaŭ momento. 

La maldekstra duono, la plej malgranda elemento maldekstre duono estas kvin. La plej malgranda elemento sur la dekstra duono estas unu. Kiu el tiuj estas pli malgranda? Unu. 

La plej malgranda elemento sur la maldekstra duono estas kvin. La plej malgranda elemento sur la dekstra duono estas du. Kio estas la plej malgranda? Du. Kaj poste persiste kvin nenion, ni povas diri kvin. 

Bone, do granda bildo, ni paŭzi dum sekundo kaj eltrovi kie ni estas. Se ni komencis la komenco, ni nun kompletigis por la totala tabelo nur unu paŝo de la _pseudocode_ kodo tie. Ni ordo la maldekstra duono de la tabelo. 

Memoru ke la originala ordono estis kvin, du, unu. Irante tra ĉi tiu procezo kaj nestumas malsupren kaj ripeti, daŭra rompi la problemo malsupren en pli malgrandajn kaj pli malgrandaj partoj, ni nun kompletigita paŝi unu el la _pseudocode_ por la tuta komenca tabelo. Ni ordigitaj lia maldekstra duono. 

Do nun ni glaciiĝas tie. Kaj nun ni ordigi la dekstra duonon de la originala tabelo. Kaj ni tuj faros tion per irante tra la sama ripeta procezo de rompado aferojn malsupren kaj tiam kunfandante ilin kune. 

Do la maldekstra duono de la ruĝa, aŭ la maldekstra duono de la dekstra duono de la originalo tabelo, Mi tuj diros estas tri. Denove, mi esti konsekvenca tie. Se vi havas neparan nombro de elementoj, ĝi ne vere gravas ĉu vi faras la maldekstra malgrandaj aŭ la dekstra unu malgranda. 

Kio gravas estas ke whenever vi renkontas tiun problemon en farado a merge, vi devas esti konsekvenca. Vi ĉu ĉiam necesas fari maldekstre malgrandaj aŭ ĉiam devas fari la dekstra flanko pli malgranda. Tie, mi elektis por ĉiam fari la maldekstra flanko pli malgranda kiam mia tabelo, aŭ mia sub-tabelo, estas de nepara grandeco. 

Tri estas ununura ero, kaj tiel ĝi estas ordo. Ni ekspluatita ke supozo dum nia tuta procezo ĝis nun. Do nun ni ordigi la dekstra duono de la dekstra duono, aŭ la dekstra duono de la ruĝa. 

Denove, ni bezonas dividi ĉi malsupren. Tio ne estas ununura elemento tabelo. Ni ne povas diveni ordo. Kaj do unue, ni tuj ordigi la maldekstra duono. 

La maldekstra duono estas ununura ero, do estas ia defaŭlte. Tiam ni iras por ordigi dekstren duonon, kio estas ununura elemento. Ĝi estas ordo defaŭlte. Kaj nun, ni povas kunfandi tiujn du kune. Kvar estas pli malgranda, kaj tiam ses estas pli malgranda. 

Denove, kion ni faris je ĉi tiu punkto? Ni ordo maldekstren duono de la dekstra duono. Aŭ revenanta al la originala koloroj kiuj tie estis, ni ordigitaj maldekstren duonon de la pli mola ruĝa. Estis origine malhela briko ruĝa kaj nun ĝi estas pli mola ruĝa, aŭ ĝi estis pli molaj ruĝa. 

Kaj tiam ni ordo la dekstra duono de la pli mola ruĝa. Nun, nu, ili estas verda denove, nur ĉar ni tuj tra procezo. Kaj ni devas ripeti tiun denove kaj denove. 

Do nun ni povas kunfandi tiujn du duonoj kune. Kaj tio estas kion ni faras ĉi tie. Do la nigran linion ĵus dividis la maldekstra duono kaj la dekstra duono de tiu speco parto. 

Ni komparu la plej malgranda valoro sur la maldekstra flanko de la tabelo aÅ­ pardonu, la plej malgranda valoro de la maldekstra duono al la plej malgranda valoro de la dekstra duono kaj trovi ke tri estas pli malgranda. Kaj nun iom de optimumigo, dekstra? Ekzistas fakte nenio lasis sur la maldekstra flanko. 

Nenio restas sur la maldekstra flanko, Do ni povas kompetente nur move-- ni povas deklari la resto de ĝi estas reale ordo kaj ĝuste najlu gxin sur, ĉar nenio alia por komparo. Kaj ni scias ke la dekstra flanko de la dekstra flanko estas ordo. 

Bone, do nun ni frostigi denove kaj eltrovi kie ni estas en la rakonto. En la totala tabelo, Kion ni plenumis? Ni reale plenumi nun paŝas unu kaj du paŝo. Ni ordo la maldekstra duono, kaj ni ordigitaj la dekstra duono. 

Do nun, ĉiu kiu restas estas por ni kunfandi tiujn du duonoj kune. Do ni komparu la plej malalta takso elemento de ĉiu duono de la tabelo siavice kaj procedi. Unu estas malpli ol tri, do oni iras. 

Du estas malpli ol tri, do du iras. Tri estas malpli ol 5, do tri iras. Kvar estas malpli ol 5, do kvar iras. Tiam kvin estas malpli ol ses, kaj ses estas ĉiuj kiuj restas. 

Nun, mi scias, ke estis multe da ŝtupoj. Kaj ni lasis multe de memoro en nia maldormo. Kaj tio estas kio tiuj grizaj kvadratoj estas. Kaj ĝi verŝajne sentis ke prenis multe pli longe ol inserción varo, bobelo varon, aŭ selektado varon. 

Sed fakte, ĉar multe de tiuj procezoj okazas samtempe time-- kio estas io ni, denove, paroli pri kiam ni parolas pri rekursio en estonta video-- tiu algoritmo reale klare estas fundamente malsama ol io ni vidis antaŭ sed estas ankaŭ signife pli efika. 

Kial estas tio? Nu, en la plej malbona kazo scenaro, ni havas fendi n elementoj supren kaj tiam recombinar ilin. Sed kiam ni recombinar ilin, kion ni faras estas esence duobligante la grandeco de la pli malgranda sensilo. Ni havas aron de unu elemento arrays ke ni efike kombini en du elemento tabeloj. Kaj tiam ni prenas tiujn du elemento tabeloj kaj kombini ilin en kvar elemento arrays, kaj tiel plu, kaj tiel plu, kaj tiel plu, ĝis ni havi solan n elemento tabelo. 

Sed kiom da doublings necesas por atingi n? Pensu reen al la telefono libro ekzemplo. Multfoje ni havas ŝiri la telefono libro en duono, kiom pli fojojn ni devos ŝiri la telefono libro en duono, se la grandeco de la telefono libro duobliĝis? Restas nur unu, ĉu ne? 

Do ekzistas ia logaritma elemento tie. Sed ni ankaŭ ankoraŭ devas almenaŭ rigardi ĉiujn de la n elementoj. Do en la plej malbona kazo scenaro, kunfandi speco kuras en n log n. Ni devas rigardi ĉiuj de la n elementoj, kaj ni devas kombini ilin kune en log n aroj de paŝoj. En la plej bona kazo scenaro, la tabelo estas perfekte ordigita. Tio estas granda. Sed bazita sur la algoritmo ni havas ĉi tie, ni ankoraŭ devas fendi kaj recombinar. Kvankam en ĉi tiu kazo, la rekombini afablas senutila. Ĝi ne estas necesa. Sed ni ankoraŭ iras tra la tuta procezo ĉiuokaze. 

Do en la plej bona kazo kaj en la plej malbona kazo, tiu algoritmo kuras en n logo n tempon. Kunfandi varo estas sendube iom trickier ol la alia ĉefa ordigado algoritmoj ni parolis pri CS50 sed estas substance pli potenca. 

Kaj do se vi iam trovas okazo bezoni ĝin aŭ uzi ĝin por ordigi granda datuma aro, Akiranta vian kapon ĉirkaŭ la ideo de rekursio tuj estos vere potenca. Kaj ĝi estas iranta fari vian programojn vere multe pli eficiente uzante kunfandi speco kontre io alia. Mi Doug Lloyd. Jen CS50.