[Muzikos grojimo] 

Doug LLOYD: Gerai, todÄl sujungti RÅ«Å¡iuoti dar vienas algoritmas , kad mes galime naudoti norÄdami iÅ¡siaiÅ¡kinti IÅ¡ masyvo elementai. Bet, kaip matysime, ji atÅ¡oko labai esminis skirtumas nuo atrankos rÅ«Å¡iuoti, burbulas RÅ«Å¡iuoti ir Ä¯terpimo RÅ«Å¡iuoti kad padaryti tai tikrai gana protingas. 

PagrindinÄ idÄja suliejimo RÅ«Å¡iuoti yra rÅ«Å¡iuoti maÅ¾esniÅ³ masyvai ir tada sujungti tuos masyvus kartu, arba sujungti them-- taigi ir rÅ«Å¡iuotÅ³ kad name--. Taip, kad sujungti rÅ«Å¡iuoti daro tai nukreipdama Ä¯rankÄ¯ vadinamas rekursija, o tai, kÄ mes ketiname kalbÄti apie netrukus, bet mes ne tikrai kalbÄjo apie dar. 

Å tai pagrindinÄ idÄja merge rÅ«Å¡iuoti. RÅ«Å¡iuoti kairÄ¯jÄ¯ pusÄ masyvo, darant prielaidÄ, kad n yra didesnis uÅ¾ 1. Ir kÄ aÅ¡ turiu galvoje, kai aÅ¡ sakau darant prielaidÄ, kad n yra didesnis uÅ¾ 1, yra, Manau, mes galime susitarti, kad jei masyvo sudaro tik vienas elementas, tai rÅ«Å¡iuojamos. Mes ne iÅ¡ tikrÅ³jÅ³ reikia nieko daryti su juo. Mes galime tik pripaÅ¾inti jÄ turi bÅ«ti iÅ¡sprÄstos. Tai tik vienas elementas. 

Taigi Pseudocode, vÄl, yra rÅ«Å¡iuoti kairÄ¯jÄ¯ pusÄ masyvo, tada rÅ«Å¡iuoti teisÄ pusÄ masyvas, tada sujungti dvi puses kartu. Dabar jau galite bÅ«ti galvoju, kad tipo tik skamba kaip jÅ«s atkalba the-- jÅ«s ne iÅ¡ tikrÅ³jÅ³ kÄ nors. JÅ«s sakote rÅ«Å¡iuoti Ä¯ kairÄ pusÄ, rÅ«Å¡iuoti tinkamÄ pusÄ, bet esate ne pasakoti man, kaip jÅ«s darote. 

Bet nepamirÅ¡ti, kad taip ilgai, kaip masyvo yra vienas elementas, mes galime pripaÅ¾inti jÄ rÅ«Å¡iuojami. Tada mes galime tiesiog sujungti juos kartu. Ir tai iÅ¡ tikrÅ³jÅ³ pagrindinÄ idÄja merge rÅ«Å¡iuoti, yra jÄ padalyti taip, kad JÅ«sÅ³ matricos dydÅ¾io vieno. Ir tada jÅ«s atkurti iÅ¡ ten. 

Sujungti RÅ«Å¡iuoti tikrai sudÄtingas algoritmas. Ir tai taip pat Å¡iek tiek sudÄtinga Ä¯sivaizduoti. Taigi tikiuosi, vizualizacija, kad aÅ¡ turime Äia padÄs jums sekti kartu. Ir aÅ¡ pabandyti mano geriausia pasakoti dalykus ir pereikite per tai Å¡iek tiek daugiau lÄtai, nei kitÅ³ tie tik tikiuosi gauti savo galvÄ aplink atsilieka merge rÅ«Å¡iuoti idÄjas. 

Taigi, mes turi tÄ patÄ¯ kaip ir Ä¯ nustatomas masyvo kiti rÅ«Å¡iavimo algoritmas video Jei maÄiau them-- Å¡eÅ¡iÅ³ elementÅ³ masyvas. Ir mÅ«sÅ³ Pseudocode kodas Äia yra tarsi kairÄ pusÄ, rÅ«Å¡iuoti tinkamÄ pusÄ, sujungti dvi puses kartu. Taigi leiskite pasinaudoti Å¡ia labai tamsiai raudonÅ³ plytÅ³ masyvas ir rÅ«Å¡iuoti kairÄ¯jÄ¯ pusÄ jo. 

Taigi Å¡iuo metu, mes ketiname ignoruoti deÅ¡inÄje stuff. Tai ten, bet mes ne tame etape dar. Mes ne rÅ«Å¡iuos teisÄ pusÄ masyvo. Mes ne RÅ«Å¡iuoti kairÄje pusÄ masyvo. Ir tik vardan , kad jis turi Å¡iek tiek daugiau aiÅ¡ku, kad aÅ¡ galiu kreiptis kas Å¾ingsnis mes apie, AÅ¡ ruoÅ¡iuosi perjungti spalva Å¡io rinkinio Ä¯ oranÅ¾inÄ. Dabar, mes vis dar kalbame apie pati kairÄje pusÄje, pirminio masyvo. Bet aÅ¡ tikiuosi, kad galÄtÅ³ kreiptis Ä¯ Ä¯vairiÅ³ daiktÅ³ spalvas, jis bus padaryti jÄ¯ Å¡iek tiek daugiau iÅ¡valyti tai, kas vyksta Äia. 

Gerai, kad dabar mes turime trijÅ³ elementÅ³ masyvas. Kaip mes rÅ«Å¡iuoti kairÄje pusÄje, tai masyvo, kuris yra dar Å¡is Å¾ingsnis? Mes stengiamÄs rÅ«Å¡iuoti Ä¯ kairÄ pusÄ plytinio raudonumo array-- kairÄ pusÄ, kuri AÅ¡ dabar spalvos oranÅ¾inÄ. 

Na, mes galime iÅ¡bandyti ir vÄl pakartokite Å¡Ä¯ procesÄ. Taigi mes vis dar viduryje bando rÅ«Å¡iuoti kairÄje pusÄje, visiÅ¡kai masyvo. KairÄje pusÄ masyvas, aÅ¡ tik ketina savavaliÅ¡kai nusprÄsti, kad kairÄ pusÄ bus maÅ¾esnis nei deÅ¡inÄs pusÄ, nes tai atsitinka sudarytas iÅ¡ trijÅ³ daliÅ³. 

Ir todÄl aÅ¡ ruoÅ¡iuosi pasakyti, kad kairÄ pusÄ kairÄje pusÄje masyvo yra tik elementas penki. Penki, bÅ«damas vienas elementas masyvas, mes Å¾inome, kaip rÅ«Å¡iuoti. Ir taip penkis rÅ«Å¡iuojamos. Mes tik ketina paskelbti, kad. Tai vienas elementas masyve. 

Taigi dabar mes surÅ«Å¡iuoti kairÄ pusÄ kairÄje half-- arba, tiksliau, mes surÅ«Å¡iuoti kairÄje pusÄje, oranÅ¾inÄs spalvos. Taigi, dabar, siekiant dar baigtas Ä¯ bendrÄ masyvo kairÄs pusÄs pusÄ, turime rÅ«Å¡iuoti tinkamÄ pusÄ iÅ¡ apelsinÅ³, ar Å¡ios medÅ¾iagos. Kaip mes tai padaryti? Na, mes turime dvi elementÅ³ masyvas. Taigi, mes galime rÅ«Å¡iuoti kairÄ¯jÄ¯ pusÄ masyvo, kuris yra du. Du yra vienas elementas. Taigi jis rÅ«Å¡iuojami pagal nutylÄjimÄ. Tada mes galime rÅ«Å¡iuoti tinkamÄ pusÄ tos masyvo, pavaizduoto porcijoje. Tai tarsi pagal nutylÄjimÄ. 

Å iuo metu tai yra pirmÄ kartÄ mes pasiekÄme suliejimo Å¾ingsnÄ¯. BaigÄme, nors mes dabar rÅ«Å¡ies Ä¯dÄtos down-- ir tai tarsi keblus dalykas su Rekursija yra Jums reikÄs iÅ¡laikyti savo galvÄ apie tai, kur mes esame. Taigi mes tarsi kairÄje pusÄ apelsinÅ³ porcijoje. 

Ir dabar, mes vidury rÅ«Å¡iavimas teisÄ pusÄ apelsinÅ³ porcijoje. Ir tame procese, mes esame dabar ketinate bÅ«ti Å¾ingsnis, sujungti dvi puses kartu. Kai paÅ¾velgiame Ä¯ dvi dalis masyvo, matome du ir vienas. Kuris elementas yra maÅ¾esnis? Vienas. 

Tada kuris elementas yra maÅ¾esnis? Na, tai dviejÅ³ ar nieko. Taigi, tai du. Taigi, dabar, tik dar kartÄ rÄmo kur mes esame kontekste, mes surÅ«Å¡iuoti kairÄ pusÄ apelsino ir teisÄ pusÄ kilmÄs. AÅ¡ Å¾inau, aÅ¡ pasikeitÄ spalvas vÄl, bet tai kur mes buvome. Ir aÅ¡ prieÅ¾astis tai padarÄ yra todÄl, kad Å¡is procesas yra ketina nesustoti, Iteracja Å¾emyn. Mes rÅ«Å¡iuojami Ä¯ kairÄ pusÄ buvusios oranÅ¾inÄ ir teisÄ pusÄ buvusios oranÅ¾inÄs spalvos. 

Dabar, mes turime sujungti tuos dvi dalis kartu per daug. Å tai Å¾ingsnis mes apie. Taigi, mes apsvarstyti visus elementai, kurie dabar Å¾alia, kairÄje pusÄje, pirminio masyvo. Ir mes sulieti tuos naudojant tÄ patÄ¯ procesÄ mes padarÄme sujungimo du ir prieÅ¡ tik vienas momentas. 

KairÄje pusÄ, maÅ¾iausias elementas kairÄje pusÄje yra penki. MaÅ¾iausias elementas teisÄ pusÄ yra vienas. Kuris iÅ¡ jÅ³ yra maÅ¾esnÄ? Vienas. 

MaÅ¾iausias elementas kairÄ pusÄ yra penki. MaÅ¾iausias elementas teisÄ pusÄ yra du. Kas yra maÅ¾iausia? Du. Ir tada galiausiai penkiÅ³ nieko, mes galime pasakyti, penki. 

Gerai, kad Big Picture, tegul atsipÅ«sti sekundÄ ir iÅ¡siaiÅ¡kinti, kur mes esame. Jei mes pradÄjome nuo PaÄioje pradÅ¾ioje mes jau baigtas bendras masyvas tik vienas Å¾ingsnis Pseudocode kodas Äia. Mes surÅ«Å¡iuoti kairÄ pusÄ masyvo. 

Prisiminkite, kad originalus Kad buvo penki, du, vienas. IÅ¡gyvena Å¡Ä¯ procesÄ ir lizdus Å¾emyn ir kartoti, toliau pertrauka problemÄ Å¾emyn Ä¯ maÅ¾esnes dalis, mes jau baigÄ vienÄ iÅ¡ Pseudocode Å¾ingsnis uÅ¾ visÄ atskaitos masyvo. Mes rÅ«Å¡iuojami savo kaire puse. 

Taigi dabar galime uÅ¾Å¡aldyti ten. O dabar tegul rÅ«Å¡iuoti teisÄ pusÄ pradinio masyvo. Ir mes ketiname daryti, kad iÅ¡gyvena tÄ patÄ¯ kartotinis procesas kad dalykÅ³ Å¾emyn ir tada sujungti juos kartu. 

Taigi kairÄ pusÄ raudona, arba yra kairÄje pusÄje iÅ¡ deÅ¡inÄs pusÄs originalo masyvas, aÅ¡ ruoÅ¡iuosi pasakyti trys. VÄlgi, aÅ¡ vis nuoseklÅ«s Äia. Jei turite nelyginis skaiÄius elementÅ³, jÄ tikrai ne klausimas, ar jums padaryti liko vienas maÅ¾esnis arba vienas teisingas maÅ¾esnis. 

Svarbu tai, kad, kai jÅ«s susiduriate su Å¡ia problema vykdant Sujungimas, jÅ«s turite bÅ«ti nuoseklÅ«s. JÅ«s arba visada reikia padaryti kairÄje pusÄje maÅ¾esnis ar visada reikia padaryti deÅ¡inÄje pusÄje maÅ¾esnis. Äia, aÅ¡ pasirinko, kad visada padaryti kairÄje pusÄje maÅ¾esnis kai mano masyvas, ar mano Sub-masyvas, yra nelyginis dydÅ¾io. 

Trys yra vienas elementas, ir todÄl ji yra rÅ«Å¡iuojami. Mes skolintomis Å¡iÄ prielaidÄ per visÄ mÅ«sÅ³ procese iki Å¡iol. Taigi dabar galime rÅ«Å¡iuoti teisÄ pusÄ deÅ¡inÄs pusÄ, arba Ä¯ deÅ¡inÄ pusÄ raudonos. 

VÄlgi, mes turime iÅ¡skaidyti tai Å¾emyn. Tai ne vienas elementas masyve. Mes negalime pripaÅ¾inti jÄ rÅ«Å¡iuojami. Ir todÄl pirmiausia, mes ketiname rÅ«Å¡iuoti yra kairÄje pusÄje. 

Kairysis pusÄ yra vienas elementas, todÄl rÅ«Å¡iuoti pagal nutylÄjimÄ. Tada mes ketiname rÅ«Å¡iuoti teisÄ pusÄ, kuri yra vienas elementas. Tai rÅ«Å¡iuojami pagal nutylÄjimÄ. Ir dabar, mes galime sujungti Å¡iÅ³ dviejÅ³ kartu. KeturiÅ³ yra maÅ¾esnis, ir Tada Å¡eÅ¡i yra maÅ¾esnis. 

VÄlgi, kÄ mes padarÄme Å¡iuo metu? Mes rÅ«Å¡iuojami Ä¯ kairÄ pusÄ deÅ¡inÄs pusÄ. Arba grÄ¯Å¾ta Ä¯ originalÄ spalvos, kad ten buvo, mes rÅ«Å¡iuojami Ä¯ kairÄ pusÄ minkÅ¡tesnÄ raudonai. IÅ¡ pradÅ¾iÅ³ buvo tamsiai plytÅ³ raudona ir dabar tai minkÅ¡tesnÄ raudona, ar tai buvo minkÅ¡tesnÄ raudona. 

Ir tada mes surÅ«Å¡iuoti teisÄ pusÄ minkÅ¡tesnÄ raudona. Dabar gerai, jie Å¾ali dar kartÄ, tik nes mes ketiname per procesÄ. Ir mes turime kartoti ir per Å¡Ä¯ daugiau. 

Taigi, dabar mes galime sujungti tuos dvi dalis kartu. Ir tai, kÄ mes darome Äia. Taigi juoda linija tiesiog suskirstyti kairÄ¯jÄ¯ pusÄ ir teisÄ pusÄ Å¡ios rÅ«Å¡ies dalis. 

Mes lyginame maÅ¾iausiÄ vertÄ kairÄje pusÄje array-- arba atsipraÅ¡au, maÅ¾iausias vertÄ kairÄs pusÄ maÅ¾iausiam vertÄs deÅ¡inÄ pusÄ ir rasti, kad trys yra maÅ¾esnis. Ir dabar, kai jos buvo optimizuoti tiek, tiesa? Yra tikrai nieko paliktas kairÄje pusÄje. 

NÄra nieko likÄ kairÄje pusÄje, todÄl mes galime efektyviai tik move-- mes galime paskelbti likusios yra iÅ¡ tikrÅ³jÅ³ rÅ«Å¡iuojamos ir tik smeigtuko jÄ apie, nes nÄra nieko dar palyginti prieÅ¡. Ir mes Å¾inome, kad deÅ¡inÄ pusÄ iÅ¡ deÅ¡inÄs pusÄs yra rÅ«Å¡iuojami. 

Gerai, kad dabar galime uÅ¾Å¡aldyti ir vÄl iÅ¡siaiÅ¡kinti, kur mes esame Ä¯ istorijÄ. Bendroje masyvas, KÄ mes pasiekiama? Mes iÅ¡ tikrÅ³jÅ³ pasiekti dabar vienas ir Å¾ingsnis dviem etapais. Mes rÅ«Å¡iuojami yra kairÄje pusÄje, o surÅ«Å¡iuota tinkamÄ pusÄ. 

Taigi dabar belieka mums sujungti Å¡ias dvi puses kartu. Taigi mes palyginti Å¾emiausias vertinami elementas kiekvieno masyvo pusÄje savo ruoÅ¾tu ir toliau. Vienas iÅ¡ jÅ³ yra maÅ¾esnis kaip trys, taip, vienas eina. 

Du yra maÅ¾esnis kaip trys, taip, du eina. Trys yra maÅ¾esnis nei 5, todÄl trijÅ³ eina. Keturi yra maÅ¾esnis nei 5, todÄl keturiÅ³ eina. Tada penki yra maÅ¾esnis nei Å¡eÅ¡iÅ³, Å¡eÅ¡i yra viskas, iÅ¡lieka. 

Dabar, aÅ¡ Å¾inau, kad buvo daug Å¾ingsniÅ³. Ir mes palikome daug atminties mÅ«sÅ³ tinklÄ. Ir tai, kÄ tie pilki kvadratÄliai. Ir tai tikriausiai jauÄiau, kad paÄmÄ daug ilgiau nei Ä¯terpimo rÅ«Å¡iuoti, burbulas RÅ«Å¡iuoti arba atranka rÅ«Å¡iuoti. 

Bet iÅ¡ tikrÅ³jÅ³, nes daug iÅ¡ Å¡iÅ³ procesÅ³ vyksta tuo paÄiu LAIKÄ_ kuri yra kaÅ¾kas, mes vÄl kalbÄti apie kai kalbame apie rekursija Ä¯ ateitÄ¯ video-- Å is algoritmas iÅ¡ tikrÅ³jÅ³ aiÅ¡kiai yra iÅ¡ esmÄs kitoks, nei nieko mes matÄme prieÅ¡ bet taip pat yra Å¾ymiai efektyviau. 

KodÄl taip yra? Na, blogiausiu scenarijaus atveju, mes turime padalinti n elementÅ³ iki ir tada rekombinuoja juos. Bet kai mes rekombinuoja jiems, kÄ mes darome iÅ¡ esmÄs dubliuoti dydis iÅ¡ maÅ¾esniÅ³ matricos. Mes turime vieno elemento krÅ«va masyvai, kad mes iÅ¡ tikrÅ³jÅ³ sujungti Ä¯ dvi elementÅ³ matricos. Ir tada mes tie du elementas masyvai ir sujungti juos kartu Ä¯ keturi element matricas ir tt, ir taip toliau, ir taip toliau, kol mes turÄti vienÄ n elementÅ³ masyvas. 

Bet kiek dubliavimÇ uÅ¾trunka gauti n? Pagalvokite atgal Ä¯ telefonÅ³ knygos pavyzdyje. Kiek kartÅ³ mes turime aÅ¡ara telefonÅ³ knyga per pusÄ, kiek daugiau kartÅ³ mes turime aÅ¡ara telefono knyga per pusÄ, jei telefono knygos dydis dvigubai? Yra tik vienas, tiesa? 

Taigi ten kaÅ¾kokia logaritminÄ elementas Äia. TaÄiau mes taip pat dar turi bent ieÅ¡koti visi n elementÅ³. Taigi, blogiausiu atveju, sujungti rÅ«Å¡iuoti veikia n log n. Mes turime paÅ¾velgti Ä¯ visi n elementÅ³, ir mes turime juos sujungti kartu log n rinkiniÅ³ Å¾ingsnius. Geriausiu atveju, masyvas puikiai rÅ«Å¡iuojami. Tai puiku. TaÄiau remiantis algoritmu mes Äia, mes vis dar turime iÅ¡skaidyti ir rekombinuoja. Nors Å¡iuo atveju, apsauginio apvalkalo rÅ«Å¡ies neveiksmingas. Tai nÄra bÅ«tinas. Bet mes vis dar eiti per visas procesas vistiek. 

Taigi geriausiu atveju o blogiausiu atveju, Å is algoritmas veikia n log n metu. Sujungti RÅ«Å¡iuoti tikrai tiek sudÄtingesnis nei kitÅ³ pagrindiniÅ³ rÅ«Å¡iavimo algoritmÅ³ mes kalbÄjome apie CS50 bet gerokai galingesnis. 

Ir todÄl, jei jÅ«s kada nors rasti proga reikia arba naudoti jÄ¯ rÅ«Å¡iuoti didelÄ duomenÅ³ rinkinys, gauti jÅ«sÅ³ galva aplink rekursijos idÄjos bus tikrai galingas. Ir jis ketina padaryti jÅ«sÅ³ programos tikrai yra daug veiksmingiau naudojant sujungti rÅ«Å¡iuoti palyginti kas nors kitas. AÅ¡ Doug Lloyd. Tai CS50.