[Mūzikas atskaņošanai] 

Doug LLOYD: Labi, tāpēc apvienot kārtošanas ir vēl viens algoritms ka mēs varam izmantot, lai sakārtotu elementi masīva. Bet kā mēs redzēsim, tas ir got ļoti būtiska atšķirība no atlases kārtot, burbulis kārtot, un ievietošanas šķirot kas padara to patiešām diezgan gudrs. 

Pamatideja sapludināšanas kārtošanas ir sakārtot mazākus blokus un tad apvienot tos bloki kopā, vai apvienot them-- tāpēc name-- jo šķiroto kārtībā. Veidā, ka apvienot veida dara tas ir, piesaistot rīks sauc rekursijas, kas ir tas, ko mēs spēsim runāt par drīz, bet mēs neesam īsti runājuši par vēl. 

Lūk Pamatideja sapludināšanas kārtošanas. Kārtot kreiso pusi no masīva, pieņemot, ka n ir lielāks par 1. Un ko es domāju, kad es saku pieņemot, ka n ir lielāks par 1, ir, Es domāju, ka mēs varam vienoties, ka, ja masīva tikai sastāv no viena elementa, tas ir sakārtoti. Mums nav tiešām nepieciešams kaut ko darīt, lai to. Mēs varam tikai atzīt to, lai tiktu sakārtoti. Tas ir tikai viens elements. 

Tātad pseudocode, atkal, ir kārtot kreiso pusi no masīva, tad šķirot labajā pusē masīvs, tad apvienot abas pusītes kopā. Tagad, jau jūs varētu būt domāšana, tas veida tikai izklausās kā jūs esat novilcināšanas the-- Jūs neesat faktiski darīt kaut ko. Jūs sakāt, šķirot kreiso puse, kārtot pareizo pusi, bet jūs neesat stāsta man, kā jūs darāt to. 

Bet atcerieties, ka tik ilgi, kamēr masīvs ir viens elements, mēs varam atzīt to sakārtoti. Tad mēs varam vienkārši apvienot tos kopā. Un tas ir faktiski fundamentāla ideja sapludināšanas veida, ir lauzt to uz leju, lai Jūsu masīvi ir lielums vienam. Un tad jūs atjaunot no turienes. 

Apvienot kārtošanas ir noteikti sarežģīts algoritms. Un tas ir arī nedaudz sarežģīti iztēloties. Tik cerams, vizualizācijas, ka es ir šeit palīdzēs jums sekot līdzi. Un es mēģināšu manos spēkos, lai stāstīt lietas un rīkojas ar šo nedaudz vairāk lēnāk nekā citiem uzņēmumiem tikai, lai, cerams, saņemt savu galvu ap aiz sapludināšanas veida idejas. 

Tāpēc mums ir tāda pati masīvs kā citas šķirošanas algoritmu video ja esat redzējuši them-- sešu elementu masīvs. Un mūsu pseudocode kods šeit ir sava kreiso pusi, kārtot pareizo pusi, apvienot abas pusītes kopā. Tātad pieņemsim šo ļoti tumši ķieģeļu sarkans masīvs un kārtot kreiso pusi no tā. 

Tāpēc pagaidām, mēs ejam ignorēt sīkumi labajā pusē. Tas ir tur, bet mēs esam ne šajā posmā vēl. Mēs esam ne kārtot tiesības puse no masīva. Mēs esam pie sava no kreisā puse no masīva. Un tikai dēļ būt mazliet vairāk skaidrs, lai es varētu atsaukties uz ko soli mēs esam par, Es esmu gatavojas, lai pārslēgtos krāsu šo komplektu uz oranžu. Tagad mēs joprojām runājam par pats kreisā puse no sākotnējā masīva. Bet es esmu cerot, ka ar to var atsaukties uz krāsas dažādiem priekšmetiem, tas būs padarīt to mazliet vairāk skaidrs, kas notiek šeit. 

Labi, tāpēc tagad mums ir trīs elementu masīvs. Kā mēs kārtotu kreiso pusi no šī masīvs, kas ir vēl šis solis? Mēs cenšamies, lai sakārtotu kreiso puse no ķieģeļu sarkanā array-- kreiso pusi no kuriem Esmu tagad oranžā. 

Nu, mēs varētu mēģināt vēlreiz atkārtot šo procesu. Tātad mēs joprojām esi vidū mēģina kārtot kreiso pusi no pilnas masīva. Kreisajā pusē no masīvs, es esmu tikai gatavojas patvaļīgi izlemt, ka kreisā puse būs mazāks nekā labajā pusē, jo tas notiek ar sastāv no trim elementiem. 

Un tāpēc es esmu gatavojas teikt, ka kreisā puse no kreisā pusē masīva ir tikai elements pieci. Pieci, būdams viens elements masīvs, mēs zinām, kā šķirot to. Un tā piecas ir sakārtots. Mēs esam tikai gatavojas paziņot, ka. Tas ir viens elements masīvs. 

Tāpēc mēs esam tagad sakārtoti kreisā puse no kreisās half-- vai drīzāk, mēs esam sakārtoti kreisā puse no oranža. Tāpēc tagad, lai vēl pilns Vispārējais Array kreisā puse, mums ir nepieciešams, lai sakārtotu pareizo pusi no apelsīnu, vai šīs lietas. Kā mēs to darām? Nu, mums ir divas elementu masīvu. Tātad, mēs varam sakārtot kreisi pusi no masīva, kas ir divi. Divi ir viens elements. Tātad, tas ir sakārtoti pēc noklusējuma. Tad mēs varam sakārtot pareizo pusi Minētās daļas masīva, viens. Tas ir sava veida pēc noklusējuma. 

Tas ir tagad pirmo reizi mēs esam sasnieguši sapludināšanas soli. Mums ir pabeigta, lai gan mēs tagad esam veida ligzdotu down-- un tas ir sava veida kutelīgs lieta ar recursion ir, Jums ir nepieciešams, lai saglabātu savu galvu par to, kur mēs esam. Tātad, mēs esam sava veida kreisi puse no apelsīnu porciju. 

Un tagad mēs esam vidū šķirošanas labajā pusē apelsīnu porciju. Un šajā procesā, mēs esam Tagad par to ir par soli, apvienot abas pusītes kopā. Kad mēs skatāmies uz divām pusēm masīva, mēs redzam divas un vienu. Kurš elements ir mazāks? One. 

Tad kurš no šiem elementiem ir mazāks? Nu, tas ir divi vai neko. Tātad, tas ir divi. Tāpēc tagad, tikai, lai atkal rāmi kur mēs esam kontekstā, mums ir sakārtoti kreisā puse no oranža un labajā pusē izcelsmi. Es zinu, es esmu mainījies krāsas atkal, bet tas, kur mēs bijām. Un iemesls, kāpēc es did this ir tāpēc, ka šis process ir gatavojas, lai saglabātu turpinās, atkārtojot leju. Mēs esam sakārtoti kreiso puse no iepriekšējā apelsīnu un labajā pusē bijušās oranža. 

Tagad mums ir nepieciešams apvienot tos, divas pusītes kopā too. Tas ir solis, mēs esam par. Tāpēc mēs uzskatām, visi elementus, kas tagad zaļā, kreiso pusi no sākotnējā masīva. Un mēs apvienot tos, izmantojot to pašu procesu mēs darījām, kas apvienojas divas un viens tikai pirms brīža. 

Kreisajā pusē, mazākais elements kreisajā pusē ir pieci. Mazākais elements labajā pusē ir viens. Kurš no tiem ir mazāks? One. 

Mazākais elements kreisā puse ir pieci. Mazākais elements labajā pusē ir divi. Kāds ir mazākais? Divi. Un tad visbeidzot pieciem nekas, mēs varam teikt, pieci. 

Labi, tik liels attēlu, pieņemsim ņemt pārtraukumu par sekundi un izdomāt, kur mēs esam. Ja mēs sākām no pašā sākumā, mēs tagad pabeigta kopējais masīvs tikko viens solis pseudocode kodu šeit. Mums ir sakārtoti kreisā puse no masīva. 

Atgādināt, ka sākotnējā rīkojums bija pieci, divi, viens. , Ejot cauri šim procesam un ligzdošanas leju un atkārtojot, turpinot lauzt problēmu lejup mazākās un mazākās daļās, tagad mēs esam pabeiguši Step viens no pseudocode visai starta masīvs. Mums ir sakārtoti tā kreiso pusi. 

Tāpēc tagad pieņemsim iesaldēt tur. Un tagad pieņemsim kārtot tiesības puse no sākotnējā masīva. Un mēs gatavojamies darīt, iet caur to pašu iteratīvs process sadalīšana lietas leju un pēc tam apvienojot tos kopā. 

Tātad kreiso pusi no sarkans, vai kreiso pusi no labajā pusē oriģināla masīvs, es esmu gatavojas teikt, ir trīs. Atkal, es esmu to konsekventi šeit. Ja jums ir nepāra elementu skaits, to nav īsti svarīgi, vai veicat kreisi viens mazāks vai pareizais mazāks. 

Svarīgi ir tas, ka ikreiz, kad jums saskaras ar šo problēmu veikšanu apvienošana, jums ir nepieciešams, lai būtu konsekventa. Jums vai nu vienmēr vajag veikt kreisā puse mazāka vai vienmēr ir nepieciešams, lai labā puse mazākas. Lūk, es esmu izvēlējusies vienmēr padarīt kreisajā pusē mazāku kad mans masīvs, vai mans sub-masīvs, ir nepāra izmēra. 

Trīs ir viens elements, un tāpēc tas ir sakārtots. Mēs esam parādi šo pieņēmumu visā mūsu visu procesu līdz šim. Tāpēc tagad pieņemsim kārtot tiesības puse no labajā pusē, vai labajā pusē sarkanā krāsā. 

Atkal, mums ir nepieciešams sadalīt šo leju. Tas nav viens elements masīvs. Mēs nevaram atzīt to sakārtoti. Un tā, pirmkārt, mēs ejam kārtot kreiso pusi. 

Kreisajā pusē ir viens elements, tāpēc tas ir sava veida pēc noklusējuma. Tad mēs ejam, lai sakārtotu tiesības puse, kas ir viens elements. Tas ir sakārtoti pēc noklusējuma. Un tagad, mēs varam apvienot šos abus kopā. Four ir mazāks, un tad seši ir mazāks. 

Atkal, ko mēs esam darījuši šajā brīdī? Mēs esam sakārtoti kreiso puse no labajā pusē. Vai dodas atpakaļ uz sākotnējo krāsas, kas bija tur, mēs esam sakārtoti kreiso puse no mīkstāka sarkanā krāsā. Tā sākotnēji bija tumšs ķieģeļu sarkans un tagad tas ir mīkstāks sarkans, vai tas bija mīkstāks sarkana. 

Un tad mēs esam sakārtoti labajā pusē mīkstāka sarkanā krāsā. Tagad, labi, viņi zaļš atkal, tikai tāpēc, ka mēs ejam cauri procesam. Un mums ir jāatkārto Tas vairāk un vairāk. 

Tāpēc tagad mēs varam apvienot tos, divas pusītes kopā. Un tas, ko mēs darām šeit. Tātad melnā līnija tikko sadalīts kreiso pusi un labajā pusē šāda veida daļas. 

Mēs salīdzinām mazāko vērtību kreisajā pusē array-- vai atvainojiet, mazākais vērtība no kreisā pusē uz vismazāko vērtību, tiesību pusi un konstatēt, ka trīs ir mazāks. Un tagad mazliet optimizāciju, vai ne? Tur tiešām nekas kreisi kreisajā pusē. 

Nav nekas atlikušais kreisajā pusē, lai mēs varētu efektīvi tikai move-- mēs varam paziņot, pārējais tas faktiski sakārtots un vienkārši sadiegšana to tālāk, jo tur nekas cits salīdzināt pret. Un mēs zinām, ka labajā pusē no labās puses ir sakārtots. 

Labi, tāpēc tagad pieņemsim iesaldēt atkal un izdomāt, kur mēs esam stāsts. Kopējā masīva, Kas mums paveikt? Mēs esam tiešām paveikt Tagad soli viens un divi soli. Mēs sakārtoti kreiso pusi, un mēs sakārtoti pareizo pusi. 

Tāpēc tagad, viss, kas paliek, ir mums apvienot šīs divas pusītes kopā. Tātad mēs salīdzinām zemākais vērtē katra puse no masīva elements savukārt un turpināt. Viens no tiem ir mazāks par trim, tāpēc viens iet. 

Divi ir mazāks par trim, tā divi iet. Trīs ir mazāks nekā 5, tāpēc trīs iet. Četri ir mazāks nekā 5, tāpēc četri iet. Tad pieci ir mazāks par sešiem, un seši ir viss, kas paliek. 

Tagad es zinu, ka bija daudz soļiem. Un mēs esam atstājuši daudz Atmiņas mūsu vārtsargam. Un tas, ko šie pelēkie laukumi ir. Un tas, iespējams, jutos kā ka paņēma ilgāk nekā ievietošanas veida daudz, burbulis kārtot, vai izvēle kārtot. 

Bet patiesībā, jo Šo procesu daudz kas notiek tajā pašā LAIKU_ kas ir kaut mēs, atkal, runāt par to, kad mēs runājam par rekursijas kādā nākotnē video-- Šis algoritms faktiski nepārprotami ir fundamentāli savādāka nekā jebkas mēs esam redzējuši iepriekš bet ir arī ievērojami efektīvāku. 

Kāpēc ir tā, ka? Nu, sliktākajā scenārijs, mums ir sadalīt n elementus up un tad rekombinēties tos. Bet, kad mēs rekombinēties tos, ko mēs darām būtībā dubultojot izmērs mazākiem masīvi. Mums ir ķekars viena elementa masīvi, ka mēs efektīvi apvienot divās elementu blokiem. Un tad mēs tos divi elementu bloki un tos apvienot četriem elementiem, bloki, un tā tālāk, un tā tālāk, un tā tālāk, kamēr mēs ir viens n elementu klāstu. 

Bet cik daudz doublings tas nepieciešams, lai saņemtu uz n? Think atpakaļ uz tālruņu grāmatu piemērs. Cik reizes mums ir asaru tālrunis grāmatu pusi, cik daudz vairāk reizes mums ir saplēst telefona grāmatu uz pusi, ja lielums telefona grāmatu dubultojies? Tur ir tikai viens, vai ne? 

Tātad tur ir daži veida logaritmiska elements šeit. Bet mēs arī vēl vismaz apskatīt visu no n elementiem. Tātad sliktākajā gadījumā, apvienot kārtot trašu n log n. Mums ir jāskatās uz visi no n elementiem, un mums ir apvienot tos kopā log n kopas soļiem. Labākajā gadījumā, masīvs ir perfekti sakārtots. Tas ir lieliski. Bet, pamatojoties uz algoritmu mums ir šeit, mums vēl ir sadalīt un rekombinēties. Lai gan šajā gadījumā krustmijas ir veida neefektīvs. Tas nav vajadzīgs. Bet mēs joprojām iet cauri viss process anyway. 

Tātad labākajā gadījumā un sliktākajā gadījumā, Šis algoritms darbojas n žurnālā n laikā. Apvienot kārtošanas noteikti ir mazliet sarežģītāk nekā citiem galvenajiem šķirošanas algoritmu mēs esam runājuši par CS50 bet ir ievērojami jaudīgāku. 

Un tāpēc, ja jūs kādreiz atrast izdevība uz to vajag vai izmantot to kārtot liels datu kopumu, kļūst galvu ap ideju recursion būs ļoti spēcīgs. Un tas notiek, lai jūsu programmas tiešām daudz efektīvāka izmantojot apvienot kārtot pret kaut ko citu. Es esmu Doug Lloyd. Tas ir CS50.