[Musik spiller] 

DOUG Lloyd: OK, så en sammenfletning sortering er endnu en algoritme at vi kan bruge til at sortere ud elementerne i et array. Men som vi skal se, er det fik en meget grundlæggende forskel fra valg sortere, boble sortere og indsættelse sortere der gør det virkelig temmelig klog. 

Den grundlæggende idé bag merge sortere er at sortere mindre arrays og derefter kombinere disse arrays sammen, eller flette them-- dermed name-- i sorteret rækkefølge. Den måde, at mergesort gør dette er ved at udnytte et værktøj kaldes rekursion, hvilket er, hvad vi kommer til at tale om snart, men vi har ikke rigtig talt om endnu. 

Her er den grundlæggende idé bag mergesort. Sortere den venstre halvdel af arrayet, under forudsætning af n er større end 1. Og hvad jeg mener, når jeg siger under forudsætning af n er større end 1 er, Jeg tror, ​​vi kan blive enige, at hvis et array kun består af et enkelt element, det er sorteret. Vi har faktisk ikke brug at gøre noget for det. Vi kan bare erklære den skal sorteres. Det er kun et enkelt element. 

Så pseudokode, igen, er sortere den venstre halvdel af arrayet, derefter sortere højre halvdel array, derefter fusionere de to halvdele sammen. Nu, allerede du kan være tænker den slags bare lyder som du lægger ud til-- du faktisk ikke gør noget. Du siger sortere venstre halvdelen, sortere højre halvdel, men du er ikke fortæller mig, hvordan du gør det. 

Men husk, at så længe et array er et enkelt element, vi kan erklære det sorteret. Så kan vi bare kombinere dem sammen. Og det er faktisk den Grundtanken bag mergesort, er at bryde det ned, så dine arrays er af størrelse én. Og så skal du genopbygge derfra. 

Mergesort er afgjort en kompliceret algoritme. Og det er også lidt kompliceret at visualisere. Så forhåbentlig, visualisering, som jeg har her vil hjælpe dig følge med. Og jeg vil prøve mit bedste for at fortælle tingene og fortsætte gennem denne lidt mere langsommere end de andre bare for at forhåbentlig få dit hoved omkring ideerne bag mergesort. 

Så vi har samme array som andre sortering algoritme videoer hvis du har set them-- en seks element array. Og vores pseudokode kode her er sortering den venstre halvdel, sortere højre halvdel, fusionere de to halvdele sammen. Så lad os tage denne meget mørke mursten rød array og sortere den venstre halvdel af den. 

Så for tiden, vil vi at ignorere de ting på højre. Det er der, men vi er ikke på dette trin endnu. Vi er ikke på sortere højre halvdel af arrayet. Vi er på sortering til venstre halvdelen af ​​arrayet. Og blot for at af at være en smule mere klar, så jeg kan henvise i hvilket trin vi er på, Jeg har tænkt mig at skifte farven på dette sæt til orange. Nu er vi stadig taler om det samme venstre halvdel af den oprindelige opstilling. Men jeg håber, at ved at kunne refererer til farverne på forskellige poster, det vil gøre det lidt mere klart, hvad der foregår her. 

OK, så nu har vi en tre element array. Hvordan kan vi sortere venstre halvdel af dette array, som stadig dette trin? Vi forsøger at sortere venstre halvdelen af ​​murstensrøde array-- den venstre halvdel af hvilke Jeg har nu farvet orange. 

Tja, vi kunne prøve og gentage denne proces igen. Så vi er stadig i midt i forsøger at sortere den venstre halvdel af den fulde matrix. Den venstre halvdel af array, jeg bare til vilkårligt beslutte, at den venstre halvdel vil være mindre end den højre halvdel, fordi dette sker for består af tre elementer. 

Og så jeg har tænkt mig at sige, at venstre halvdel af den venstre halvdel array er blot elementet fem. Fem, er et enkelt element array, vi ved, hvordan at sortere det. Og så fem sorteres. Vi er lige kommer til at erklære, at. Det er et enkelt element array. 

Så vi har nu sorteres venstre halvdel af venstre half-- eller rettere, har vi sorteret de venstre halvdel af orange. Så nu, med henblik på at der stadig komplet den samlede arrayets venstre halvdel, vi nødt til at sortere den højre halvdel af den orange, eller det her. Hvordan gør vi det? Tja, vi har en to element array. Så vi kan sortere venstre halvdel af grupperingen, som er to. To er et enkelt element. Så det er ordnet som standard. Så kan vi sortere højre halvdel af den del af arrayet, den ene. Det er slags som standard. 

Det er nu for første gang Vi har nået en sammenfletning skridt. Vi har gennemført, selv om vi nu slags indlejret down-- og det er en slags tricky ting med rekursion, du skal holde din hoved om, hvor vi er. Så vi har en slags venstre halvdelen af ​​den orange del. 

Og nu er vi midt i sortering den højre halvdel af den orange del. Og i den proces, vi er nu ved at være på trinnet, fusionere de to halvdele sammen. Når vi ser på de to halvdele af array, ser vi to og en. Hvilket element er mindre? One. 

Så hvilket element er mindre? Nå, det er to eller ingenting. Så det er to. Så nu, bare for igen indramme hvor vi er i sammenhæng, Vi har sorteret det venstre halvdel af den orange og den højre halvdel af oprindelsen. Jeg ved, jeg har ændret farverne igen, men det er, hvor vi var. Og grunden til at jeg gjorde dette skyldes, at denne proces er kommer til at holde ud, iteration ned. Vi har sorteret venstre halvdelen af ​​den tidligere appelsin og den højre halvdel af den tidligere orange. 

Nu er vi nødt til at fusionere dem to halvdele sammen også. Det er det skridt, vi er på. Så vi overveje alle de elementer, der nu grønne, den venstre halvdel af den oprindelige opstilling. Og vi flette dem ved hjælp af den samme proces vi gjorde for at sammenlægge to og man blot for et øjeblik siden. 

Den venstre halvdel, den mindste element på venstre halvdel er fem. Det mindste element på højre halvdel er en. Hvilke af dem er mindre? One. 

Det mindste element på den venstre halvdel er fem. Det mindste element på højre halvdel er to. Hvad er den mindste? To. Og så til sidst fem og noget, kan vi sige fem. 

OK, så store billede, lad os tage en pause for en anden og finde ud af hvor vi er. Hvis vi startede fra begyndelsen, vi har nu afsluttet for den samlede matrix lige et trin i pseudokode kode. Vi har sorteret det venstre halvdel af arrayet. 

Husk på, at den oprindelige ordre var fem, to, en. Ved at gå gennem denne proces og indlejring ned og gentage, fortsætter med at bryde problemet ned i mindre og mindre dele, Vi har nu afsluttet trin en af ​​pseudokode for hele udgangspunkt array. Vi har sorteret sit venstre halvdel. 

Så lad os nu fryse der. Og lad os nu sortere ret halvdelen af ​​den oprindelige opstilling. Og vi vil gøre ved at går gennem den samme iterative processen med at bryde ting ned og derefter flette dem sammen. 

Så den venstre halvdel af rød eller venstre halvdel af den højre halvdel af den oprindelige array, jeg har tænkt mig at sige, er tre. Igen, jeg er konsistent her. Hvis du har et ulige antal elementer, det er faktisk ligegyldigt, om du gør den venstre mindre eller den rigtige mindre. 

Det afgørende er, at når du støder på dette problem i at gennemføre en sammenfletning, skal du være konsekvent. Du enten altid behøver at gøre en venstre side mindre eller altid nødt til at gøre højre mindre. Her har jeg valgt at altid gøre venstre side mindre da min array, eller min sub-array, er af et ulige størrelse. 

Tre er et enkelt element, og det er sorteret. Vi har gearede denne antagelse i hele vores proces hidtil. Så lad os nu sortere ret halvdelen af ​​den højre halvdel, eller den højre halvdel af den røde. 

Igen, vi er nødt til at splitte det ned. Dette er ikke et enkelt element array. Vi kan ikke erklære det sorteret. Og så første, vi vil at sortere den venstre halvdel. 

Den venstre halvdel er et enkelt element, så det er slags som standard. Så vi kommer til at sortere det rigtige halvdelen, som er et enkelt element. Det er ordnet som standard. Og nu, vi kan flette de to sammen. Fire er mindre, og derefter seks er mindre. 

Igen, hvad har vi gjort på dette punkt? Vi har sorteret venstre halvdelen af ​​den højre halvdel. Eller gå tilbage til den oprindelige farver, der var der, Vi har sorteret venstre halvdelen af ​​det blødere rød. Det var oprindeligt en mørk mursten rød og nu er det en blødere rød, eller det var en blødere rød. 

Og så har vi sorteret de højre halvdel af blødere rød. Nu, godt, de er grønne igen, bare fordi vi går igennem en proces. Og vi er nødt til at gentage dette igen og igen. 

Så nu kan vi flette dem to halvdele sammen. Og det er, hvad vi gør her. Så den sorte linje lige delte den venstre halvdel og den højre halvdel af denne art del. 

Vi sammenligner den mindste værdi på venstre side af array-- eller undskyld mig, den mindste værdien af ​​den venstre halvdel til den mindste værdi af retten halvdelen og opdager, at tre er mindre. Og nu lidt af en optimering, ikke? Der er faktisk ikke noget tilbage på den venstre side. 

Der er intet tilbage på venstre side, så vi kan effektivt bare move-- vi kan erklære resten af ​​det er faktisk sorteres og bare tack det på, fordi der ikke er noget andet at sammenligne med. Og vi ved, at den højre side af den højre side sorteres. 

OK, så lad os nu fryse igen og regne ud, hvor vi er i historien. I den samlede array, hvad har vi opnået? Vi har faktisk udrette nu trin et og trin to. Vi sorteret den venstre halvdel, og vi sorteret højre halvdel. 

Så nu, er der kun tilbage for os at fusionere de to halvdele sammen. Så vi sammenligner laveste værdsatte element i hver halvdel af arrayet til gengæld og fortsætte. Den ene er mindre end tre, så man går. 

To er mindre end tre, så to går. Tre er mindre end 5, så tre går. Fire er mindre end 5, så fire går. Så fem er mindre end seks, og seks er alt der er tilbage. 

Nu ved jeg, der var en masse trin. Og vi har efterladt en masse hukommelse i vores kølvand. Og det er, hvad de grå firkanter er. Og det sandsynligvis følte der fandt en meget længere end indsættelse sortere, boble sortere, eller udvælgelse slags. 

Men faktisk, fordi en Mange af disse processer sker på samme time-- hvilket er noget, vi får igen, taler om, når vi taler om rekursion i en fremtidig video-- denne algoritme faktisk klart er fundamentalt anderledes end noget vi har set før men er også betydeligt mere effektiv. 

Hvorfor det? Tja, i værste case scenario, vi har at opdele n elementer op og derefter kombinere dem. Men når vi rekombinere dem, hvad vi laver er dybest set en fordobling af størrelsen af ​​de mindre arrays. Vi har en flok af ét element arrays som vi effektivt kombinere i to element arrays. Og så tager vi dem to element arrays og kombinere dem sammen i fire element arrays, og så videre, og så videre, og så videre, indtil vi have en enkelt n element array. 

Men hvor mange fordoblinger tager det at komme til n? Tænk tilbage til telefonbog eksempel. Hvor mange gange skal vi rive telefonbogen i halve, hvor mange flere gange har vi til at rive telefonbogen i halve, hvis størrelsen af ​​telefonbogen fordoblet? Der er bare én, ikke? 

Så der er en slags logaritmiske element her. Men vi har også stadig nødt til i det mindste se på alle de n elementer. Så i værste fald, mergesort kører i n log n. Vi er nødt til at se på alle de n elementer, og vi er nødt til at kombinere dem sammen i log n sæt af trin. I bedste fald, arrayet er perfekt sorteret. Det er godt. Men baseret på den algoritme, vi har her, vi stadig nødt til at splitte og kombinere. Selv om der i dette tilfælde rekombination er slags ineffektiv. Det er ikke nødvendigt. Men vi stadig gå igennem hele processen alligevel. 

Så i bedste fald og i værste fald, denne algoritme kører i n log n tid. Mergesort er absolut en smule tricky end de andre store sorterings- algoritmer vi har talt om CS50, men er væsentligt mere kraftfuld. 

Og så hvis du nogensinde finde lejlighed til at brug for det eller bruge den til at sortere en store datasæt, at få dit hoved omkring ideen om rekursion kommer til at være virkelig kraftfuld. Og det kommer til at gøre din programmer virkelig langt mere effektiv hjælp mergesort versus noget andet. Jeg er Doug Lloyd. Det er CS50.