[Muusika mängib] 

DOUG LLOYD: OK, nii ühendamise Sorteeri on järjekordne algoritm et saame kasutada praakima elemendid massiivi. Aga nagu me näeme, see sai väga põhimõtteline erinevus valikust omamoodi, mull sorteerida ja sisestamise omamoodi et oleks tõesti kaval. 

Põhiidee ühendamine Sorteeri on sorteerida väiksem massiivid ja siis ühendada need massiivid koos, või ühendada them-- seega name-- sorteeritud järjekorras. Nii, et liita omamoodi teeb see on võimendades vahend nimetatakse rekursiooni, mis on see, mida me ei kavatse rääkida kiiresti, kuid me ei ole tõesti rääkisime veel. 

Siin põhiidee ühendamine omamoodi. Sorteeri vasakul pool massiivi, eeldades n on suurem kui 1. Ja mida ma mõtlen, kui ma ütlen eeldades n on suurem kui 1 on, Ma arvan, et me saame kokku leppida, et kui massiivi koosneb ainult ühe elemendi, see on järjestatud. Me tegelikult ei vaja midagi teha sellega. Me lihtsalt kuulutada välja sorteerida. See on ainult üks element. 

Nii pseudokoodi on jällegi Kuvatud vasakule poole massiiv, siis sorteerida õige pool massiivi, siis ühendada kaks poolt kokku. Nüüd juba siis võiks olla mõtlesin, et mingi lihtsalt kõlab nagu sa oled hakanud välja the-- sa tegelikult ei tee midagi. Ütled sorteeri vasakul poole, sorteerida õige poole, aga sa ei räägi mulle, kuidas sa teed seda. 

Kuid pidage meeles, et nii kaua, kui massiivi on ühe elemendi, saame kuulutada järjestatud. Siis saame lihtsalt ühendada need kokku. Ja see on tegelikult põhiline idee ühendada sorteerida, on jaotada see nii, et Sinu massiivid on suurus üks. Ja siis te taastada sealt. 

Merge omamoodi on kindlasti keeruline algoritm. Ja see on ka natuke keeruline ette kujutada. Loodetavasti, visualiseerimine, et ma on siin aitab teil jälgida mööda. Ja ma püüan oma parima, et jutustada asju ja sõita läbi selle natuke rohkem aeglasemalt kui teised need lihtsalt loodetavasti saan oma peaga ümber ideede ühendamine omamoodi. 

Nii et meil on sama rida nagu teiste sorteerimisalgoritm videod Kui olete näinud them-- kuue element massiivi. Ja meie pseudokoodi koodi siin on omamoodi Vasakul pool, sorteerida õige poole, ühendada kaks poolt kokku. Võtame seda väga tume telliskivi punaseks massiivi ja sorteerida vasakule poole. 

Nii praegu, me ei kavatse ignoreerida asju õige. See on olemas, kuid me oleme mitte, et samm veel. Me ei ole hetkel Sorteeri paremal pool massiivi. Oleme juures omamoodi vasakul pool massiivi. Ja just huvides olemise veidi rohkem selge, nii et ma ei viita mida sammu me oleme, Ma lähen lülitada värvi see komplekt oranžiks. Nüüd, me ikka räägime Sama vasakule poole algse massiivi. Aga ma loodan, et nad saaksid vaadake värve erinevaid objekte, see teen selle natuke rohkem selge, mis toimub siin. 

OK, nii et nüüd on meil kolm elementi massiivi. Kuidas sorteerida vasakule poole sellest massiiv, mis on ikka see samm? Me püüame sorteerida vasakul pool telliskivi punane array-- Vasakul pool sellest Olen nüüd oranž. 

Noh, me võiksime proovida ja Seda protsessi korratakse uuesti. Nii et me oleme ikka Keset üritab sorteerida Vasakul pool tervet rida. Vasakpoolne poole massiiv, ma lähen lihtsalt suvaliselt otsustada, et vasakul pool kasutatakse väiksemat paremal poolel, sest see juhtub koosneb kolmest osast. 

Ja nii ma öelda, et vasakul poolel vasakul poolel massiivi on lihtsalt element viis. Viis, olles üheks osaks massiiv, me teame, kuidas sortida. Ja nii viis on järjestatud. Me elame kuulutada, et. See on ühe elemendi massiivist. 

Nii et me oleme nüüd sorteeritud Vasakul pool vasakul half-- või pigem oleme sorteeritud Vasakul pool oranž. Nüüd, et ikka täielik üldine massiiv vasakul pool, vajame sorteerida õige poole oranž, või seda kraami. Kuidas me seda teeme? Noh, meil on kaks elementi massiivi. Nii saame sorteerida vasakule poole massiivi, mis on kaks. Kaks on ühe elemendi. Nii see on järjestatud vaikimisi. Siis on võimalik järjestada paremal pool Selle järjestuse osa, üks. See on omamoodi vaikimisi. 

See on nüüd esmakordselt oleme jõudnud ühendamise samm. Oleme valmis, kuigi me nüüd selline pesitseda down-- ja see on omamoodi keeruline asi rekurrentselt on, sa pead hoidma oma pea kohta, kus me oleme. Nii me oleme omamoodi vasakul poole apelsini osa. 

Ja nüüd, me oleme keset sorteerimine paremal pool oranž osa. Ja selles protsessis oleme nüüd hakkab olema samm, ühendada kaks poolt kokku. Kui me vaatame kaheks pooleks massiivi, näeme kahe ja ühe. Milline element on väiksem? Üks. 

Siis mis element on väiksem? Noh, see on kaks või midagi. Seega on kaks. Nüüd, lihtsalt uuesti kadreerida kus me oleme kontekstis oleme sorteeritud Vasakul pool oranz ja paremal pool päritolu. Ma tean, et ma olen muutnud värvi uuesti, kuid see, kus me olime. Ja põhjus, miks ma tegin seda seetõttu, et see protsess on läheb edasi minema, iterating alla. Me oleme järjestatud vasakult pool endise oranž ja paremal pool endise oranž. 

Nüüd on vaja ühendada need kaheks pooleks kokku ka. See on samm me oleme. Nii arvame kõik elemendid, mis on nüüd rohelised, vasakul poolel algse massiivi. Ja me ühinevad need kasutades sama protsessi tegime ühinevad kaks ja üks hetk tagasi. 

Vasakpoolne poole, väikseim element vasakul pool on viis. Kõige väiksem element paremal pool on üks. Kumb neist on väiksem? Üks. 

Kõige väiksem element Vasakul pool on viis. Kõige väiksem element paremal pool on kaks. Milline on väikseim? Kaks. Ja siis lõpuks viis midagi, me ei saa öelda viie. 

OK, nii suur pilt, olgem pausi teist ja aru saada, kus me oleme. Kui me alustasime Algusest peale oleme on nüüd lõpule üldine massiiv lihtsalt üks samm pseudokoodi koodi siin. Meil on sorteeritud Vasakul pool massiivi. 

Tuletame meelde, et esialgse Selleks oli viis, kaks, üks. Minnes läbi selle protsessi ja pesitsevate alla ja korrates, jätkates murda probleemi väiksemateks ja väiksemateks osadeks, oleme nüüd valmis samm üks pseudokoodi kogu lähtekohaks massiivi. Meil on järjestatud selle vasakul poolel. 

Nüüd oletame külmuda seal. Ja nüüd on omamoodi õigus poole algse massiivi. Ja me ei kavatse teha, et läbimas sama iteratiivne Protsessi purustamine asju ette ja siis ühinevad nad kokku. 

Nii vasakul poolel punane või vasakule poole õiguse poole originaal massiiv, ma lähen ütlen on kolm. Jällegi, ma oleks järjepidevad. Kui teil on paaritu elementide arv, seda ei ole tegelikult küsimus, kas teete jäänud üks väiksem või õige väiksemad. 

Oluline on, et iga kord, kui kogevad seda probleemi läbi ühendamise, pead olema järjekindel. Sa kas alati vaja teeb vasakul äärel väiksem või alati vaja teha paremal pool väiksem. Siin ma olen valinud alati teha vasakpoolne väiksem kui minu rida, või minu sub-massiivi, on paaritu suurus. 

Kolm on ühe elemendi, ja nii see on järjestatud. Me oleme võimendatud, et eeldus kogu meie kogu protsessi siiani. Vaatame nüüd sorteeri õigus poolel õigus poole, või paremal pool punane. 

Jällegi, me peame jagama seda maha. See ei ole ühe elemendi massiivist. Me ei saa kuulutada järjestatud. Ja nii esimese, me ei kavatse sorteeri vasakul pool. 

Vasakpoolne poolel on üksikosa, nii et see on omamoodi vaikimisi. Siis me lähme sorteerida õige poole, mis on üksikosa. See on järjestatud vaikimisi. Ja nüüd, saame liita need kaks kokku. Neli on väiksem ja siis kuus on väiksem. 

Jällegi, mida me oleme teinud sel hetkel? Me oleme järjestatud vasakult poolel õigus poole. Või läheb tagasi algse värvid, mis olid seal, oleme järjestatud vasakult pool pehmem punaseks. Algselt oli tume tellis punane ja nüüd on pehmem punane, või see oli pehmem punane. 

Ja siis oleme sorteeritud paremal pool pehmem punane. Nüüd, samuti on nad jälle roheliseks, lihtsalt sest me oleme läbimas protsessi. Ja me peame kordama see ikka ja jälle. 

Nüüd saame liita need kaheks pooleks kokku. Ja see, mida me siin teeme. Nii must joon ainult jagatud vasakul pool ja paremal pool selline osa. 

Võrdleme väikseim väärtus vasakul küljel array-- või vabandage, väikseim väärtus vasakul pool väikseima väärtuse õigus poole ja leiavad, et kolm on väiksem. Ja nüüd natuke optimeerimine, eks? Seal on tegelikult midagi vasakule vasakul küljel. 

Ei ole midagi jäänud vasakul küljel, et saaksime tõhusalt lihtsalt move-- saame kuulutada ülejäänud on tegelikult sorteerida ja lihtsalt pühitakse see kohta, sest seal on midagi muidu võrreldakse. Ja me teame, et paremal pool paremale küljele on järjestatud. 

OK, nii et nüüd lähme uuesti külmutage ja aru saada, kus me oleme lugu. Üldises massiiv, mida oleme saavutanud? Me oleme tegelikult täita Nüüd astub üks ja teine ​​etapp. Me järjestatud vasakult poole võrra ja me järjestatud paremal pool. 

Nüüd on kõik, mis jääb üle ühendada need kaks poolt kokku. Nii me võrdleme madalaim väärtus element iga poole massiivi omakorda ja edasi. Üks on vähem kui kolm, nii et üks läheb. 

Kaks on vähem kui kolm, nii et kaks läheb. Kolm on alla 5, seega kolme läheb. Neli on alla 5, seega nelja läheb. Siis viis on vähem kui kuus, ja kuus on kõik, mis jääb. 

Nüüd ma tean, et oli palju samme. Ja me oleme jätnud palju mälu meie kiiluvees. Ja see, mida need hallid ruudud on. Ja see ilmselt tundus, et võttis palju enam kui sisestamise sorteerida, mull Sorteeri või valikut omamoodi. 

Aga tegelikult, sest palju neid protsesse toimuvad samal AEG_ mida me tulen jälle räägime, kui me räägime recursion tulevases video-- See algoritm tegelikult selgelt on põhimõtteliselt teistsugune kui midagi oleme näinud vaid on ka oluliselt tõhusamaks. 

Miks nii? Noh, kõige hullem stsenaariumi korral on meil jagada n elementi üles ja siis rekombineerumise neid. Aga kui me rekombineerumise need, mida me teeme on põhimõtteliselt kahekordistada suurus väiksemate massiive. Meil on hunnik üks element massiivid, et me tegelikult ühendada kahte elementi massiivi. Ja siis me võtame need kaks elementi massiivi ja nende alusel koostada nelja elemendi massiivid, ja nii edasi, ja nii edasi, ja nii edasi, kuni me on üks n element massiivi. 

Aga kui palju kahekordistumine see võtab, et saada n? Mõtle tagasi telefoniraamatust näiteks. Mitu korda me peame kiskuma telefoniraamatust pooleks, kui palju korda on meil pisar telefoniraamat poole, kui suurus telefoniraamatust kahekordistunud? Seal on lihtsalt üks, eks? 

Nii et mingisugune logaritmiline element siin. Aga meil on ka veel vähemalt vaata kõiki n elementi. Nii et halvimal juhul liita omamoodi töötab n log n. Me peame vaatama kõik n elemente, ja meil on neid omavahel kombineerida koos log n toimingust. Parimal juhul stsenaarium, massiiv on täiesti järjestatud. See on suurepärane. Aga põhineb algoritm meil siin, meil on veel jagada ja rekombineerumise. Kuigi selles asjas recombining on selline ebaefektiivne. Ei ole vaja. Aga meil on veel läbida kogu protsessi niikuinii. 

Nii parimal juhul ja halvimal juhul See algoritm töötab n log n korda. Merge omamoodi on kindlasti veidi keerukam kui teised peamised sorteerimise algoritme oleme rääkinud CS50 kuid on oluliselt võimsam. 

Ja kui sa kunagi leida võimalus seda vajavad või kasutada seda sortida suur andmekogum, saada oma pea ümber idee recursion saab olema väga võimas. Ja see läheb teha oma programmid tõesti palju tõhusam kasutades liita omamoodi versus midagi muud. Ma olen Doug Lloyd. See on CS50.