[TÓNLIST spila] 

DOUG LLOYD: OK, svo sameinast tegund er enn annar reiknirit að við getum notað til að raða út þætti array. En eins og við munum sjá, það er got a mjög grundvallarmunur frá Val tagi, kúla raða, og innsetning tegund að gera það í raun nokkuð snjall. 

Grunnhugmyndin á bak við sameinast tegund er að raða minni fylki og síðan sameina þá fylki saman, eða sameina them-- þess vegna name-- í raðaða röð. Leiðin að Mergesort er þetta er með því að fá meira tól heitir endurkvæmni, sem er hvað við erum að fara að tala um fljótlega, en við höfum í raun ekki talað um enn. 

Hér er Grunnhugmyndin á bak mergesort. Raða vinstri helming fylkisins, að því gefnu n er meiri en 1. Og hvað ég meina þegar ég segi að því gefnu n er meiri en 1 er, Ég held að við getum verið sammála um að ef array aðeins samanstendur af einni þáttur, það er flokkað. Við gerum ekki raunverulega þörf að gera neitt við það. Við getum bara lýsa það að vera flokkaður. Það er aðeins einn þáttur. 

Svo sauðakóðanum, aftur, er raða vinstri hluta fylkisins, þá raða rétt helmingur array, þá sameinast tvo helminga saman. Nú, þegar þú gætir verið hugsa, það konar bara hljómar eins og þú ert að setja á the-- þú ert í raun ekki að gera neitt. Þú ert að segja raða vinstri helmingur, raða rétt helminginn, en þú ert ekki að segja mér hvernig þú ert að gera það. 

En muna að svo lengi sem fylki er einn þáttur, við getum lýst það flokkað. Þá getum við bara sameina þær. Og það er í raun grunnhugsun að baki sameiningu tagi, er að brjóta það niður þannig að fylki eru af stærð einni. Og þá þú endurbyggja þaðan. 

Mergesort er ákveðið flókið reiknirit. Og það er líka svolítið flókið að sjón. Svo vonandi er visualization sem ég hafa hér mun hjálpa þér að fylgja með. Og ég ætla að reyna mitt besta til að sagt hlutina og halda áfram í gegnum þetta aðeins meira hægar en hinar bara að vonandi fá höfuð þitt um hugmyndum að baki sameiningu tagi. 

Þannig að við höfum sama array sem er Önnur flokkun reiknirit myndbönd ef þú hefur séð them-- sex þáttur array. Og sauðakóðanum númerið okkar hér er tegund vinstri helminginn, raða rétt helminginn, sameina tvo helminga saman. Svo skulum við taka þetta mjög dökk múrsteinn rauður array og raða vinstri helmingur af því. 

Svo um sinn, við erum að fara að hunsa efni á hægri. Það er þarna, en við erum ekki á þeim skref enn. Við erum ekki á að raða hægri helminginn af fylkisins. Við erum á einhverskonar vinstri helmingur fylkisins. Og bara fyrir sakir af því að vera a lítill fleiri ljóst, svo ég geti átt hvað skref sem við erum á, Ég ætla að kveikja á litur þetta sett til appelsínugult. Nú erum við enn að tala um Sama vinstri helminginn af upprunalegu array. En ég vona að með því að vera fær um að vísa til litum ýmsu atriði, það mun gera það svolítið meira ljóst hvað er að gerast hér. 

OK, svo nú höfum við þrír þáttur array. Hvernig eigum við að raða vinstri hluta þessa array, sem er enn þetta skref? Við erum að reyna að raða vinstri helmingur múrsteinn rauður array-- vinstri helminginn af sem Ég hef nú litað appelsínugult. 

Jæja, við reynum og endurtaka þetta ferli aftur. Þannig að við erum enn í miðja þess að reyna að raða vinstri helminginn af fullum fylkisins. Vinstri helmingur array, ég ætla bara að fara að geðþótta ákveðið að vinstri helmingur verði minni en hægri hluta, vegna þess að þetta gerist samanstanda af þremur þáttum. 

Og svo ég ætla að segja að vinstri helminginn af vinstri hluta fylkisins er bara þáttur fimm. Fimm, að vera einn þáttur array, við vitum hvernig á að flokka það. Og svo fimm er flokkaður. Við erum bara að fara að lýsa því yfir að. Það er einn þáttur array. 

Þannig að við höfum nú flokkuð sem vinstri helminginn af vinstri half-- eða öllu heldur, höfum við raðað í vinstri helminginn af appelsína. Svo nú, í því skyni að enn lokið vinstri helmingur heildar Array er, við þurfum að raða rétt helminginn af appelsínu, eða þessu efni. Hvernig gerum við það? Jæja, höfum við tveggja þátturinn array. Svo við getum raða vinstri hluta fylkisins, sem er tveir. Tvö er einn þáttur. Svo það er flokkað sjálfgefið. Þá getum við raða rétt helminginn af þeim hluta fylkisins, einn. Það er tegund af sjálfgefið. 

Þetta er nú í fyrsta sinn við höfum náð sameiningar- skref. Við höfum lokið, þótt við erum nú eins konar hreiður down-- og það er tegund af erfiður Málið með endurkvæmni er, þú þarft að halda þínum höfuð um hvar við erum. Þannig að við höfum konar vinstri helmingur af appelsínugula hluta. 

Og nú erum við í miðju flokka hægri helminginn af appelsínugula hluta. Og í því ferli, við erum nú um að vera á þrepi, sameina tvo helminga saman. Þegar við skoðum helminga fylkisins, sjáum við tvo og einn. Hvaða þáttur er minni? Einn. 

Þá er hver þáttur minni? Jæja, það er tveir eða ekkert. Svo er það tveir. Svo nú, bara til aftur ramma þar sem við erum í samhengi, við höfum raðað í vinstri helminginn af Orange og hægri helminginn af uppruna. Ég veit að ég hef breytt litum aftur, en það er þar sem við vorum. Og ástæða þess að ég gerði þetta er vegna þess að þetta ferli er fara að halda áfram, iterating niður. Við höfum flokkað vinstri helmingur af fyrrum appelsínugult og hægri helminginn af fyrrum appelsína. 

Nú þurfum við að sameinast þeim tvennt saman líka. Það er skref sem við erum á. Þannig að við teljum allt í þættir sem eru nú grænt, vinstri helminginn af upprunalegu array. Og við sameinast þeim með því að nota sömu aðferð við gerðum til að sameina tvær og einn bara í smá stund síðan. 

Vinstri helmingur, minnstu þáttur á vinstri helming er fimm. Minnsta þáttur á hægri helminginn er einn. Hver af þeim er minni? Einn. 

Minnsta þáttur á vinstri helmingurinn er fimm. Minnsta þáttur á hægri helminginn er tveggja. Hvað er minnsti? Two. Og þá loks fimm og ekkert, getum við sagt fimm. 

OK, svo stór mynd, við skulum taka hlé í smástund og reikna út hvar við erum. Ef við byrjuðum frá upphafi, við hefur nú lokið fyrir heildar array bara eitt skref í sauðakóðanum kóða hér. Við höfum raðað í vinstri hluta fylkisins. 

Muna að upprunalega röð var fimm, tveir, einn. Með því að fara í gegnum þetta ferli og verpa niður og endurtaka, að halda áfram að brjóta vandamál niður í smærri og smærri hluta, við höfum nú lokið stíga einn af sauðakóðanum fyrir allt byrjun fylkisins. Við höfum flokkað vinstri helming þess. 

Svo nú skulum frysta það. Og nú skulum raða rétt helmingur af upprunalegu array. Og við erum að fara að gera það fara í gegnum það sama endurtekningu Ferlið að brjóta það niður og síðan sameina þá saman. 

Þannig að vinstri hluta rauður eða vinstri helming á hægri hluta af upprunalegu array, ég ætla að segja er þrír. Aftur, ég er að vera í samræmi hér. Ef þú ert stakur fjöldi staka, það skiptir ekki máli hvort þú gerir vinstri ein minni eða rétt ein minni. 

Það sem skiptir máli er að þegar þér fundur this vandamál í framkvæmd a sameinast, þú þarft að vera í samræmi. Þú annað hvort alltaf þurfa að gera vinstri hlið minni eða alltaf þurfa að gera hægra megin minni. Hér hef ég valið að alltaf gera vinstri hlið minni þegar array minn eða minn undir-array, er stakur stærð. 

Þrjú er einn þáttur, og svo það er flokkað. Við höfum skuldsett það forsendu í gegnum allt ferli okkar svo langt. Svo nú skulum raða rétt helmingur hægri hluta, eða hægri helminginn af rauðu. 

Aftur, við þurfum að skipta þessu niður. Þetta er ekki einn þáttur array. Við getum ekki sagt það flokkað. Og svo fyrst, við erum að fara að raða vinstri helming. 

Vinstri helmingurinn er einn þáttur, svo það er tegund af sjálfgefið. Þá erum við að fara að raða rétt helming, sem er einn þáttur. Það er raðað sjálfkrafa. Og nú, við getum sameinast þessir tveir saman. Fjögur er minni, og þá er sex minni. 

Aftur, hvað höfum við gert á þessum tímapunkti? Við höfum flokkað vinstri helmingur hægri hluta. Eða fara aftur til upprunalega litir, sem þar bjuggu, við höfum raðað vinstri helmingur mýkri rauðu. Það var upphaflega dökk múrsteinn rauður og nú er það mýkri rautt, eða það var mýkri rautt. 

Og þá höfum við raðað í hægri helminginn af mýkri rauðu. Nú, jæja, þá eru þeir aftur græn, bara vegna þess að við erum að fara í gegnum ferli. Og við verðum að endurtaka þetta aftur og aftur. 

Svo nú getum við sameinast þeim tvennt saman. Og það er það sem við gerum hér. Svo svarta línu bara skipt vinstri helming og hægri helminginn af þessu tagi hluta. 

Við berum saman lægsta gildi á vinstri hlið af the array-- eða afsaka mig, minnstu gildi vinstri hluta í minnstu gildi hægri helmingur og kemst að því að þrjú er minni. Og nú dálítið af hagræðingu, ekki satt? Það er í raun ekkert vinstri á vinstri hlið. 

Það er ekkert eftir á vinstri hlið, svo við getum duglegur bara move-- við getum lýst restin af því er í raun flokkaður og bara tittur það á, vegna þess að það er ekkert annað að bera saman gegn. Og við vitum að hægri hlið af hægri hlið er flokkaður. 

OK, svo nú skulum frysta aftur og reikna út þar sem við erum í sögunni. Í heild array, Hvað höfum við náð? Við höfum í raun náð nú skref eitt og stíga tvö. Við raðað vinstri helming, og Við raðað rétt helminginn. 

Svo nú, allt sem helst er fyrir okkur að sameina þessa tvo helminga saman. Svo við saman lægstu metin þáttur hvers hluta fylkisins aftur og halda áfram. Eitt er minna en þrír, svo maður fer. 

Tvö er minna en þrír, svo tveir fer. Þrjú er minna en 5, þannig þrír fer. Fjögur er minna en 5, þannig fjórir fer. Þá er fimm minna en sex, og sex er allt sem er eftir. 

Nú veit ég, það var mikið af skrefum. Og við höfum vinstri mikið minni í kjölfar okkar. Og það er það sem þeir gráum reitum eru. Og það var sennilega svona tók mikið lengur en Innsetningarröðun, kúla tegund, eða val konar. 

En í raun, vegna þess að mikið af þessum ferlum eru að gerast á sama time-- sem er eitthvað sem við munum aftur, tala um þegar við tölum um endurkvæmni í framtíðinni video-- Þetta reiknirit raun greinilega er í grundvallaratriðum öðruvísi en nokkuð við höfum séð áður en er einnig verulega skilvirkari. 

Afhverju er það? Jæja, í versta falli, höfum við að skipta n þætti upp og þá sameinum þær. En þegar við sameinum þá, hvað við erum að gera er í grundvallaratriðum að tvöföldun á Stærð minni fylki. Við höfum fullt af einn þáttur fylki sem við í raun sameina í tvo staka fylki. Og þá erum við að taka þær tvær þáttur fylki og sameina þær í fjögur frumefni fylki, og svo framvegis, og svo framvegis, og svo framvegis, þar til við hafa einn n þátturinn array. 

En hversu margir helmingsstækkanir tekur það að fá að n? Hugsaðu til baka í símaskrá dæmi. Hversu oft við þurfum að rífa símaskrá í tvennt, hversu margir fleiri sinnum eigum við að rífa símaskrá í tvennt, ef stærð símaskránni tvöfaldast? Það er bara eitt, ekki satt? 

Þannig að það er einhvers konar lógaritmískum þáttur hér. En við einnig enn að minnsta kosti líta á alla þá N þætti. Svo í versta falli, Mergesort keyrir n log n. Við verðum að líta á öllu af N þáttum, og við verðum að sameina þá saman log n sett af skrefum. Í besta falli, array er fullkomlega raðað. Það er frábært. En miðað við reiknirit sem við höfum hér, við höfum enn að skipta og sameinum. Þó að í þessu tilfelli, recombining er góður af árangurslaus. Það er ekki þörf. En við förum samt í gegnum allt ferlið engu að síður. 

Svo í besta tilfelli og í versta tilfelli, Þetta reiknirit keyrir n log n tíma. Mergesort er ákveðið dálítið trickier en aðrar helstu flokkun reiknirit við höfum talað um CS50 en er verulega öflugri. 

Og svo ef þú finnur alltaf tilefni til að þurfa það eða til að nota það til að raða a stór gögnum, fá höfuðið í kringum þá hugmynd endurkvæmni er að fara að vera mjög öflugur. Og það er að fara að gera þinn forrit í raun mun skilvirkari nota Mergesort móti allt annað. Ég er Doug Lloyd. Þetta er CS50.