[Music kucheza] 

DOUG LLOYD: Sawa, hivyo kuunganisha aina hii bado ni algorithm mwingine kwamba tunaweza kutumia aina nje mambo ya safu. Lakini kama tutaweza kuona, ni got tofauti ya msingi sana kutoka uteuzi aina, Bubble aina, na kuingizwa aina kwamba kufanya hivyo ni kweli pretty wajanja. 

Wazo msingi nyuma ya kuunganisha aina ni aina arrays ndogo na kisha kuchanganya arrays wale pamoja, au kuunganisha them-- hivyo name-- ili Iliyopangwa. Njia ambayo kuunganisha aina gani hii ni kwa leveraging chombo aitwaye kujirudia, ambayo ni nini tunakwenda kuwa na kuzungumza juu hivi karibuni, lakini sisi si kweli aliyesema kuhusu bado. 

Hapa ni wazo la msingi la kuunganisha aina. Aina nusu kushoto wa safu, kuchukua n ni kubwa kuliko 1. Na nini maana mimi wakati mimi kusema kuchukua n ni kubwa kuliko 1 ni, Nadhani tunaweza kukubaliana kwamba kama safu tu lina kipengele moja, ni vyema. Hatuna haja kweli kufanya kitu chochote na hiyo. Tunaweza tu kuyatangaza ya kutatuliwa. Ni tu kipengele moja. 

Hivyo pseudocode, tena, ni aina kushoto nusu ya safu, kisha kutatua nusu ya haki safu, kisha kuunganisha sehemu mbili kwa pamoja. Sasa, tayari unaweza kuwa kufikiri, ni aina ya tu Inaonekana kama wewe ni kuweka mbali the-- wewe si kweli kufanya kitu chochote. Wewe ni kusema kutatua kushoto nusu, aina nusu haki, lakini wewe si kuwaambia mimi jinsi wewe kufanya hivyo. 

Lakini kumbuka kwamba kwa muda mrefu kama safu ni kipengele moja, tunaweza kuitangaza vyema. Basi tunaweza tu kuchanganya yao pamoja. Na hiyo ni kweli msingi Dhana ya aina kuunganisha, ni kwa kuvunja chini ili arrays yako ni ya kipimo kimoja. Na kisha kujenga upya kutoka huko. 

Kuunganisha aina ni dhahiri algorithm ngumu. Na pia ni kidogo ngumu kupiga taswira. Hivyo hopefully, taswira ya kuwa mimi na hapa kukusaidia kufuata pamoja. Na mimi itabidi kujaribu bora yangu kusimulia mambo na kuendelea kwa njia hii zaidi kidogo polepole zaidi kuliko wale wengine tu hopefully kupata kichwa yako karibu mawazo nyuma ya kuunganisha aina. 

Hivyo tuna safu sawa na mengine ya kuchagua video algorithm kama wameweza kuona them-- sita kipengele safu. Na pseudocode kificho yetu hapa ni aina nusu kushoto, kutatua nusu ya haki, kuunganisha sehemu mbili kwa pamoja. Basi hebu kuchukua hii giza sana tofali nyekundu safu na aina kushoto nusu yake. 

Hivyo kwa wakati huu, tunakwenda kupuuza mambo juu ya haki. Ni pale, lakini tuko si wakati kwamba hatua bado. Sisi siyo katika aina nusu haki ya safu. Tupo aina kushoto nusu ya safu. Na tu kwa ajili kuwa kidogo zaidi wazi, hivyo siwezi kutaja kwa nini hatua sisi ni juu, Mimi nina kwenda kubadili rangi ya kuweka hii kwa rangi ya machungwa. Sasa, bado tuko kuzungumza juu ya sawa kushoto nusu ya awali safu. Lakini nina matumaini kwamba kwa kuwa na uwezo wa rejea rangi ya vitu mbalimbali, kutakuwa na kufanya hivyo zaidi kidogo wazi nini kinaendelea hapa. 

OK, hivyo kwa sasa tuna tatu kipengele safu. Je, sisi kutatua kushoto nusu ya hii safu, ambayo bado hatua hii? Sisi ni kujaribu kutatua kushoto nusu ya tofali nyekundu array-- nusu ya kushoto ya ambayo Nimekuwa sasa rangi ya machungwa. 

Naam, tunaweza kujaribu na kurudia utaratibu huu tena. Hivyo bado tuko katika katikati ya kujaribu aina nusu ya kushoto ya safu kamili. Nusu ya kushoto ya safu, mimi nina kwenda tu kiholela kuamua kwamba nusu ya kushoto itakuwa ndogo kuliko nusu wa kulia, kwa sababu hii hutokea kwa wajumbe wa mambo matatu. 

Na hivyo mimi nina kwenda kusema kwamba kushoto nusu ya nusu ya kushoto ya safu ni tu kipengele tano. Tano, kuwa kipengele moja safu, tunajua jinsi ya aina yake. Na hivyo tano ni Iliyopangwa. Sisi ni kwenda tu kutangaza kwamba. Ni moja ya kipengele safu. 

Hivyo tumekuwa sasa yamepangwa kushoto nusu ya half-- kushoto au tuseme, tumekuwa yamepangwa kushoto nusu ya machungwa. Hivyo sasa, ili bado kamili ujumla safu ya kushoto nusu, tunahitaji kutatua nusu ya haki ya machungwa, au mambo haya. Je, sisi kufanya hivyo? Naam, tuna mbili kipengele safu. Ili tuweze kutatua kushoto nusu wa safu, ambayo ni mbili. Mbili ni kipengele moja. Hivyo ni yamepangwa kwa chaguo-msingi. Basi tunaweza kutatua nusu ya haki ya kuwa sehemu ya safu, moja. Hiyo ni aina ya kama chaguo-msingi. 

Hii ni mara ya kwanza sasa tumekuwa kufikiwa kuunganisha hatua. Tuna kukamilika, ingawa sisi ni sasa aina ya Furushi down-- na hiyo ni aina ya gumu Jambo kwa kujirudia ni, unahitaji kuweka yako kichwa kuhusu ambapo sisi ni. Hivyo tumekuwa aina ya kushoto nusu ya sehemu ya machungwa. 

Na sasa, tuko katikati ya kuchagua nusu haki ya fungu machungwa. Na katika mchakato huo, sisi ni sasa kuhusu kuwa juu ya hatua, kuunganisha sehemu mbili kwa pamoja. Tunapoangalia nusu mbili wa safu, tunaona mbili na moja. Ambayo kipengele ni kubwa? Moja. 

Basi ni ipi katika kipengele ni kubwa? Naam, ni mbili au chochote. Hivyo ni mbili. Hivyo sasa, tu tena sura ambapo sisi ni katika mazingira, sisi yamepangwa kushoto nusu ya machungwa na nusu haki ya asili. Najua nimekuwa iliyopita rangi tena, lakini hapo ndipo tulikuwa. Na sababu mimi alifanya hivyo ni kwa sababu mchakato huu ni kwenda kuendelea, iterating chini. Tumekuwa yamepangwa kushoto nusu ya machungwa zamani na nusu haki ya machungwa zamani. 

Sasa, tunahitaji kuunganisha wale nusu mbili pamoja pia. Hiyo ni hatua sisi ni juu. Hivyo tunaona wote wa mambo ambayo ni sasa kijani, nusu ya kushoto ya awali safu. Na sisi kuunganisha wale kutumia utaratibu huo tulivyofanya kwa kuunganisha mbili na moja tu wakati iliyopita. 

Kushoto nusu, ndogo kipengele juu ya nusu kushoto ni watano. Ndogo kipengele katika nusu haki ni moja. Ni yupi kati ya hao ni kubwa? Moja. 

Ndogo kipengele katika nusu kushoto ni watano. Ndogo kipengele katika nusu haki ni mbili. Nini madogo? Mbili. Na kisha mwisho tano na kitu, tunaweza kusema tano. 

OK, hivyo picha kubwa, hebu kuchukua mapumziko kwa ajili ya pili na takwimu nje ambapo sisi ni. Kama sisi kuanza kutoka mwanzo kabisa, sisi sasa kukamilika kwa safu kwa ujumla tu hatua moja ya pseudocode kificho hapa. Tuna yamepangwa kushoto nusu ya safu. 

Kumbuka kwamba awali Ili ilikuwa tano, mbili, moja. Kwa kwenda kupitia mchakato huu na nesting chini na kurudia, kuendelea kuvunja tatizo chini katika sehemu ndogo ndogo, sisi sasa kukamilika hatua moja ya pseudocode kwa kuanzia nzima safu. Tuna yamepangwa nusu wake wa kushoto. 

Hivyo sasa hebu kufungia huko. Na sasa hebu kutatua haki nusu ya awali safu. Na tunakwenda kufanya hivyo kwa kwenda kwa iterative sawa mchakato wa kuvunja mambo chini na kisha kuunganisha yao kwa pamoja. 

Hivyo nusu ya kushoto ya nyekundu, au nusu ya kushoto ya nusu ya awali ya haki safu, mimi nina kwenda kusema ni tatu. Tena, mimi nina kuwa thabiti hapa. Kama una isiyo ya kawaida idadi ya vipengele, ni kweli haina kujali kama kufanya kushoto moja ndogo au ndogo moja ya haki. 

Kitu muhimu ni kwamba wakati wowote kukutana na tatizo hili katika kuendesha kuunganisha, unahitaji kuwa thabiti. Wewe ama daima haja ya kufanya kushoto upande ndogo au siku zote haja ya kufanya upande wa kulia ndogo. Hapa, nimekuwa waliochaguliwa kwa siku zote kufanya kushoto upande ndogo wakati safu yangu, au yangu ndogo ya safu, ni ya kawaida isiyo ya kawaida. 

Tatu ni kipengele moja, na hivyo ni vyema. Tumekuwa leveraged dhana kwamba katika mchakato yetu yote hadi sasa. Hivyo sasa hebu kutatua haki nusu ya nusu haki, au nusu haki ya nyekundu. 

Tena, tunahitaji umegawanyika hii chini. Hii si moja ya kipengele safu. Hatuwezi kutangaza ni yamepangwa. Na hivyo kwanza, tunakwenda kutatua nusu kushoto. 

Nusu kushoto ni kipengele moja, hivyo ni aina ya kama chaguo-msingi. Kisha tunakwenda aina haki nusu, ambayo ni kipengele moja. Ni yamepangwa kwa chaguo-msingi. Na sasa, tunaweza kuunganisha hizo mbili pamoja. Nne ni ndogo, na kisha sita ni ndogo. 

Tena, tumefanya nini katika hatua hii? Tumekuwa yamepangwa kushoto nusu ya nusu ya haki. Au kwenda nyuma ya awali rangi wale waliokuwa pale, tumekuwa yamepangwa kushoto nusu ya nyekundu laini. Awali ilikuwa matofali giza nyekundu na sasa ni laini nyekundu, au ilikuwa ni nyekundu laini. 

Na kisha tumekuwa yamepangwa nusu haki ya nyekundu laini. Sasa, vizuri, wao uko kijani tena, tu kwa sababu tunakwenda kupitia mchakato. Na tuna kurudia juu ya hili na zaidi. 

Hivyo sasa tunaweza kuunganisha wale mbili halves pamoja. Na kwamba ni nini tunafanya hapa. Hivyo mstari mweusi tu kugawanywa nusu ya kushoto na nusu haki ya huu sehemu namna yo yote. 

Sisi kulinganisha thamani ndogo upande wa kushoto wa array-- au udhuru kwangu, ndogo thamani ya nusu ya kushoto kwa ndogo thamani ya haki nusu na kupata kwamba tatu ni ndogo. Na sasa kidogo ya Biashara, sawa? Kuna kweli hakuna kitu kushoto upande wa kushoto. 

Kuna kitu iliyobaki upande wa kushoto, ili tuweze kwa ufanisi tu move-- tunaweza kutangaza mapumziko ya ni kweli yamepangwa na tu upepo ni juu, kwa sababu kuna kitu mwingine kulinganisha dhidi ya. Tunajua kwamba upande wa kulia ya upande wa kulia ni Iliyopangwa. 

OK, hivyo sasa hebu kufungia tena na kufikiri ambapo sisi ni katika hadithi. Katika safu kwa ujumla, nini sisi yametimia? Tumekuwa kweli kukamilisha sasa hatua moja na hatua mbili. Sisi yamepangwa nusu ya kushoto, na sisi yamepangwa nusu ya haki. 

Hivyo sasa, kwamba bado ni kwa ajili yetu kuunganisha wale nusu mbili pamoja. Hivyo sisi kulinganisha chini yenye thamani kipengele cha kila nusu ya safu kwa upande wake na kuendelea. Moja ni chini ya tatu, hivyo moja unaendelea. 

Mbili ni chini ya tatu, hivyo wawili unaendelea. Tatu ni chini ya 5, hivyo tatu unaendelea. Nne ni chini ya 5, hivyo vinne unaendelea. Kisha tano ni chini ya sita, na sita ni kwamba bado. 

Sasa, Mimi najua kuwa na mengi ya hatua. Na tumekuwa kushoto mengi ya kumbukumbu katika wake zetu. Na kwamba ni nini viwanja wale Gray ni. Na pengine waliona kama kwamba alichukua muda mrefu kuliko kuingizwa aina, Bubble aina, au uteuzi aina. 

Lakini kwa kweli, kwa sababu mengi ya taratibu hizi yanayotokea katika time-- sawa ambayo ni kitu tutaweza, tena, majadiliano juu wakati sisi majadiliano juu kujirudia katika siku zijazo video-- algorithm hii kwa kweli wazi ni kimsingi tofauti kuliko kitu chochote tumeona kabla lakini pia ni kwa kiasi kikubwa ufanisi zaidi. 

Kwanini hivyo? Naam, katika hali mbaya zaidi kesi, tuna kugawa n vipengele up na kisha mawazoni mwao. Lakini wakati sisi mawazoni yao, nini sisi ni kufanya kimsingi mara dufu ukubwa wa arrays ndogo. Tuna kundi la kipengele moja arrays kwamba sisi kwa ufanisi kuchanganya katika arrays mbili kipengele. Na kisha tunachukua wale arrays mbili kipengele na kuchanganya yao pamoja katika arrays kipengele wanne, na kadhalika, na kadhalika, na kadhalika, mpaka sisi kuwa moja n kipengele safu. 

Lakini doublings wangapi gani kuchukua ili kupata n? Fikiria nyuma kitabu cha simu mfano. Ni mara ngapi kufanya tuna machozi kitabu cha simu katika nusu, jinsi wengi zaidi mara kufanya tuna machozi kitabu cha simu katika nusu, kama ukubwa wa kitabu cha simu mara mbili? Kuna mmoja tu, sawa? 

Hivyo kuna baadhi ya aina ya logarithmic kipengele hapa. Lakini pia bado wana angalau kuangalia yote ya n vipengele. Hivyo katika mazingira ya kesi mbaya, kuunganisha aina anaendesha katika n logi n. Tuna kuangalia wote wa mambo n, na tuna kuchanganya yao pamoja katika logi n seti ya hatua. Katika bora kesi, safu kikamilifu yamepangwa. Hiyo ni kubwa. Lakini kulingana na algorithm sisi hapa, bado tuna kugawa na mawazoni. Ingawa katika kesi hiyo, recombining ni aina ya ufanisi. Ni si inahitajika. Lakini sisi bado kwenda kwa njia ya mchakato mzima hata hivyo. 

Hivyo katika kesi bora na katika hali mbaya zaidi, algorithm hii anaendesha katika n logi n mara. Kuunganisha aina ni dhahiri kidogo trickier kuliko nyingine kuu kuchagua algorithms tumekuwa aliyesema kuhusu CS50 lakini ni kikubwa na nguvu zaidi. 

Na hivyo kama wewe milele kupata nafasi ya haja yake au kuitumia kutatua kubwa seti data, kupata kichwa wako karibu wazo la recursion ni kwenda kuwa kweli nguvu. Na ni kwenda kufanya yako Mipango kweli ufanisi mkubwa zaidi kutumia kuunganisha aina dhidi ya kitu kingine chochote. Mimi nina Doug Lloyd. Hii ni CS50.