[MUSIK SPELA] 

DOUG Lloyd: OK, så en sammanslagning sortera är ännu en algoritm att vi kan använda för att sortera ut elementen i en array. Men när vi får se, det har fått en mycket grundläggande skillnad från val Sortera, bubbla sortera och insättningssortering som gör det egentligen ganska smart. 

Den grundläggande idén bakom merge sort är att sortera mindre arrayer och sedan kombinera dessa matriser tillsammans, eller slå samman them-- hence name-- i sorterad ordning. Det sätt som merge sort gör detta är genom att utnyttja ett verktyg kallas rekursion, vilket är vad vi kommer att tala om snart, men vi har inte riktigt pratat om ännu. 

Här är den grundläggande idén bakom merge sort. Sortera den vänstra halvan av uppsättningen, förutsatt n är större än 1. Och vad jag menar när jag säger förutsatt n är större än 1 är, Jag tror att vi kan enas om att om en array endast består av ett enda element, det sorterade. Vi egentligen inte behöver att göra något för det. Vi kan bara förklara den ska sorteras. Det är bara ett enda element. 

Så pseudokod, återigen, är sortera vänstra halvan av uppsättningen, sedan sortera högra halv arrayen, sedan slå samman de två halvorna. Nu, redan du kan vara tänker, det slags bara låter som du skjuter the-- du faktiskt inte göra någonting. Du säger sortera vänster hälften, sortera den högra halvan, men du inte berättar mig hur du gör det. 

Men kom ihåg att så länge en array är ett enda element, vi kan förklara den sorteras. Då kan vi bara kombinera ihop dem. Och det är faktiskt Grundtanken bakom merge sort, är att bryta ner det så att dina arrayer är storlek en. Och sedan bygga därifrån. 

Merge sort är definitivt en komplicerad algoritm. Och det är också lite komplicerat att visualisera. Så förhoppningsvis, visualisering som jag har här kommer att hjälpa dig att följa med. Och jag ska göra mitt bästa för att berätta saker och gå igenom detta lite mer långsammare än de andra bara för att förhoppningsvis få ditt huvud runt idéerna bakom merge sort. 

Så vi har samma array som andra sorteringsalgoritm videor Om du har sett them-- en sex elementgrupp. Och vår pseudokoden här är typ den vänstra halvan, sortera den högra halvan, slå samman de två halvorna. Så låt oss ta det mycket mörk tegelröd array och sortera den vänstra halvan av det. 

Så för närvarande, vi kommer att ignorera saker på höger sida. Det är där, men vi är inte vid detta steg ännu. Vi är inte på sortera högra halvan av matrisen. Vi är på sortera vänster halv av arrayen. Och bara för sakens skull att vara lite mer klar, så jag kan hänvisa vad steg vi är på, Jag kommer att växla Färgen på denna uppsättning till orange. Nu, vi pratar fortfarande om Samma vänstra halvan av den ursprungliga arrayen. Men jag hoppas att genom att kunna Se färgerna på olika poster, Det kommer att göra det lite mer klart vad som händer här. 

OK, så nu har vi en tre elementgrupp. Hur ska vi sortera vänstra halvan av detta array, som fortfarande är det här steget? Vi försöker att sortera vänster halv av tegelröd array-- den vänstra halvan av vilka Jag har nu färgad orange. 

Tja, vi kan prova och upprepa denna process igen. Så vi är fortfarande i mitten för att försöka sortera den vänstra halvan av full uppsättning. Den vänstra halvan av array, jag ska bara godtyckligt besluta att den vänstra halvan kommer att vara mindre än den högra halv, eftersom det händer består av tre delar. 

Och så ska jag säga att vänstra halv av den vänstra halv arrayen är bara elementet fem. Fem, är ett enda element array, vi vet hur man sorterar det. Och så fem sorteras. Vi kommer bara att förklara det. Det är ett enda element array. 

Så vi har nu sorteras vänstra halv av den vänstra half-- eller snarare, har vi sorterat vänstra halvan av orange. Så nu, för att ändå komplett den totala uppsättningen vänstra halvan, vi måste sortera högra halvan i orange, eller det här. Hur gör vi det? Tja, vi har en två elementgrupp. Så vi kan sortera vänstra halvan av arrayen, vilket är två. Två är ett enda element. Så det är sorterade efter standard. Då kan vi sortera högra halvan av den del av arrayen, det en. Det är typ av som standard. 

Detta är nu första gången Vi har nått en sammanslagning steg. Vi har genomfört, men Vi bevakar nu typ av kapslade down-- och det är typ av knepigt sak med rekursion är, du behöver för att hålla din huvudet om var vi är. Så vi har sorts vänster halv av den orange partiet. 

Och nu, vi är i mitten av sortering den högra halvan av den orange delen. Och i den processen, vi är nu på väg att bli på steget, slå samman de två halvorna. När vi tittar på de två halvorna av arrayen, ser vi två och en. Vilket element är mindre? En. 

Sedan vilket element är mindre? Tja, det är två eller ingenting. Så det är två. Så nu, bara för att återigen rama där vi är i sitt sammanhang, Vi har sorterat vänstra halvan av den orange och den högra halvan av origo. Jag vet att jag har ändrat färgerna igen, men det är där vi var. Och anledningen till att jag gjorde detta beror på att denna process är kommer att fortsätta, iteration ned. Vi har sorterat vänster hälften av den tidigare apelsin och den högra halvan av den tidigare apelsin. 

Nu måste vi slå ihop dem två halvorna också. Det är det steg vi är på. Så vi anser alla element som är nu grönt, den vänstra halvan av den ursprungliga arrayen. Och vi slå samman de med användning av samma förfarande vi gjorde för att slå samman två och en bara en stund sedan. 

Den vänstra halvan, den minsta element på den vänstra halvan är fem. Det minsta elementet på den högra halvan är en. Vilken av dem är mindre? En. 

Det minsta elementet på den vänstra halvan är fem. Det minsta elementet på den högra halvan är två. Vad är det minsta? Två. Och sedan slutligen fem och ingenting, kan vi säga fem. 

OK, så helheten, låt oss ta en paus för en sekund och räkna ut var vi är. Om vi ​​startade från början, vi har nu avslutats för den totala matrisen bara ett steg i pseudokoden här. Vi har sorterat vänstra halv av arrayen. 

Minns att det ursprungliga För var fem, två, ett. Genom att gå igenom denna process och häckar ner och upprepa, fortsätter att dela upp problemet upp i mindre och mindre delar, Vi har nu avslutat steg en av pseudokoden för hela start arrayen. Vi har sorterat sitt vänstra halvan. 

Så nu ska vi frysa där. Och nu ska vi sortera rätt hälften av den ursprungliga matrisen. Och vi kommer att göra det genom att gå igenom samma iterativa processen att bryta ner saker och sedan slå samman dem tillsammans. 

Så den vänstra halvan av rött, eller den vänstra halv av den högra hälften av den ursprungliga array, jag kommer att säga är tre. Återigen, jag är konsekvent här. Om du har en udda antal element, det spelar egentligen ingen roll om du gör det vänstra mindre eller rätten en mindre. 

Det viktiga är att när du stöta på detta problem i dirigering en sammanslagning, måste du vara konsekvent. Du behöver alltid antingen göra en vänster sida mindre eller alltid behöver göra den högra sidan mindre. Här har jag valt att alltid göra vänster sida mindre när min samling, eller min underuppställning är av ett udda storlek. 

Tre är ett enda element, och så den sorteras. Vi har leveraged detta antagande under hela vår process hittills. Så nu ska vi sortera rätt halv av den högra halv, eller den högra halvan av den röda. 

Återigen måste vi dela ner det. Detta är inte en enda elementgrupp. Vi kan inte förklara den sortering. Och så först, vi kommer att sortera den vänstra halvan. 

Den vänstra halvan är ett enda element, så det är typ av som standard. Sedan ska vi sortera rätt halv, vilket är ett enda element. Det är sorterade efter standard. Och nu, vi kan slå ihop dessa två tillsammans. Fyra är mindre, och då sex är mindre. 

Återigen, vad har vi gjort vid denna tidpunkt? Vi har sorterat vänster hälften av den högra halvan. Eller gå tillbaka till den ursprungliga färger som var där, Vi har sorterat vänster halv av den mjukare rött. Det var ursprungligen en mörk tegel rött och nu är det en mjukare rött, eller om det var en mjukare rött. 

Och sedan har vi sorteras högra halvan av mjukare rött. Nu, ja, de är grön igen, precis eftersom vi går igenom en process. Och vi måste upprepa detta om och om igen. 

Så nu kan vi slå ihop dem två halvor tillsammans. Och det är vad vi gör här. Så den svarta linjen bara delas den vänstra halvan och den högra halvan av detta slag del. 

Vi jämför det minsta värdet på vänstra sidan av array-- eller ursäkta mig, den minsta värdet på den vänstra halv till det minsta värdet av den högra hälften och upptäcker att tre är mindre. Och nu lite av en optimering, eller hur? Det finns faktiskt inget kvar på den vänstra sidan. 

Det finns inget kvar på vänster sida, så vi kan på ett effektivt sätt bara move-- vi kan deklarera resten av det är faktiskt sorteras och bara lägga fram det på, eftersom det finns inget annat att jämföra mot. Och vi vet att den högra sidan av den högra sidan sorteras. 

OK, så nu ska vi frysa igen och räkna ut var vi befinner oss i berättelsen. I den totala matrisen, vad har vi åstadkommit? Vi har faktiskt åstadkomma Nu steg ett och steg två. Vi sorterade den vänstra halvan, och Vi sorterade den högra halvan. 

Så nu är allt som återstår för oss att slå samman de två halvorna. Så vi jämför det lägsta värderade elementet i varje halv av uppsättningen i sin tur och fortsätter. En är mindre än tre, så man går. 

Två är mindre än tre, så två går. Tre är mindre än 5, så tre går. Fyra är mindre än 5, så fyra går. Sedan fem är mindre än sex, och sex är allt som återstår. 

Nu, jag vet, det var en hel del åtgärder. Och vi har lämnat en hel del minne i vårt kölvatten. Och det är vad de grå rutorna är. Och det kändes nog som det tog en mycket längre än insättningssortering, bubbla sort eller val slag. 

Men egentligen, eftersom en Många av dessa processer händer på samma time-- vilket är något som vi ska, återigen, tala om när vi talar om rekursion i ett framtida video-- denna algoritm faktiskt klart är i grunden annorlunda än något vi har sett förut men är också betydligt mer effektiv. 

Varför? Tja, i värsta scenario, har vi att dela n element upp och sedan kombinera dem. Men när vi återförenas dem, vad vi gör är i princip en fördubbling av storleken av de mindre matriser. Vi har ett gäng ett element arrayer som vi effektivt kombinera till två elementuppsättningar. Och sedan tar vi dem två elementuppsättningar och kombinera ihop dem till fyra elementuppsättningar, och så vidare, och så vidare, och så vidare, tills vi har en enda n elementgrupp. 

Men hur många fördubblingar tar det att komma till n? Tänk tillbaka till telefonboken exempel. Hur många gånger ska vi behöva riva telefonboken på mitten, hur många fler tider måste vi riva telefonboken i halv, om storleken på telefonboken fördubblats? Det finns bara en, eller hur? 

Så det finns någon form av logaritmisk inslag här. Men vi har fortfarande också att åtminstone titta på alla av de n element. Så i värsta fall, merge sort körs i n log n. Vi måste titta på alla av de n elementen, och vi måste kombinera dem tillsammans i log n uppsättningar av steg. I bästa fall, matrisen är perfekt sorteras. Toppen. Men baserat på den algoritm som vi har här, vi har fortfarande att dela och kombinera. Även i detta fall, den rekombination är typ av ineffektiv. Det behövs inte. Men vi fortfarande gå igenom hela processen ändå. 

Så i bästa fall och i värsta fall, denna algoritm körs i n log n tid. Merge sort är definitivt lite knepigare än de andra stora sorteringsalgoritmer Vi har pratat om CS50 men är betydligt mer kraftfull. 

Och så om du någonsin tillfälle att behöva det eller att använda den för att sortera en stor datamängd, få huvudet kring idén om rekursion kommer att bli riktigt kraftfull. Och det kommer att göra din program verkligen mycket effektivare använder merge sort kontra något annat. Jag är Doug Lloyd. Detta är CS50.