[MUSIC SPILLE] 

DOUG LLOYD: OK, så et flette sort er nok en algoritme som vi kan bruke til å sortere ut elementene i en matrise. Men som vi skal se, det har en veldig fundamental forskjell fra utvalget sortere, boble sortere og innsetting sort som gjør det egentlig ganske smart. 

Den grunnleggende ideen bak merge sorter er å sortere mindre arrays og deretter kombinere disse arrays sammen, eller flette them-- derav name-- i sortert rekkefølge. Måten fusjonere slags gjør dette er ved å utnytte et verktøy kalt rekursjon, som er hva vi skal snakke om å bli snart, men vi har egentlig ikke snakket om ennå. 

Her er den grunnleggende ideen bak merge sort. Sortere venstre halvdel av tabellen, forutsatt at n er større enn 1. Og hva jeg mener når jeg sier forutsatt at n er større enn 1 er, Jeg tror vi kan være enige om at hvis en matrise bare består av et enkelt element, det er sortert. Vi har ikke egentlig trenger å gjøre noe til det. Vi kan bare erklære det som skal sorteres. Det er bare et enkelt element. 

Så pseudokode, igjen, er sortere venstre halvdel av tabellen, deretter sortere høyre halvdel av tabellen, deretter slå sammen de to halvdelene sammen. Nå, allerede kan du være tenkning, den slags bare høres ut som du sette av the-- du faktisk ikke gjør noe. Du sier sortere venstre halvparten, sortere høyre halvdel, men du er ikke å fortelle meg hvordan du gjør det. 

Men husk at så lenge en matrise er et enkelt element, vi kan erklære det sortert. Da kan vi bare kombinere dem sammen. Og det er faktisk den Grunntanken bak merge sort, er å bryte det ned slik at arrays er av størrelse en. Og så du gjenoppbygge derfra. 

Flett typen er definitivt en komplisert algoritme. Og det er også litt komplisert å visualisere. Så forhåpentligvis, visualisering som jeg har her vil hjelpe deg å følge med. Og jeg skal prøve mitt beste for å fortelle ting og gå gjennom dette litt mer saktere enn de andre bare for å forhåpentligvis få hodet rundt ideene bak merge sort. 

Så vi har samme utvalg som andre sorteringsalgoritme videoer Hvis du har sett them-- en seks element array. Og vår pseudokoden her er liksom venstre halvdel, sortere høyre halvdel, fusjonere de to halvdelene sammen. Så la oss ta dette veldig mørk mursteinsrød matrise og sortere igjen halvparten av det. 

Så for tiden, vi skal å ignorere ting til høyre. Den er der, men vi er ikke i det skrittet enda. Vi er ikke i form til høyre halvdel av tabellen. Vi er på liksom venstre halvparten av tabellen. Og bare for moro skyld for å være litt mer klart, så jeg kan referere til hva skritt vi er på, Jeg kommer til å slå Fargen på dette settet til oransje. Nå er vi fremdeles snakker om samme venstre halvdel av den opprinnelige matrisen. Men jeg håper at ved å være i stand til å refererer til fargene på ulike elementer, det vil gjøre det litt mer klart hva som skjer her. 

OK, så nå har vi en tre-element array. Hvordan vi sorterer gjør den venstre halvdelen av dette array, som fortsatt er dette trinnet? Vi prøver å sortere venstre halvparten av mursteinsrød array-- venstre hvorav halvparten Jeg har nå farget oransje. 

Vel, vi kan prøve og gjenta denne prosessen på nytt. Så vi er fortsatt i midten av prøver å sortere den venstre halvdel av en fullstendig matrise. Den venstre halvdel av matrise, jeg bare går å vilkårlig bestemme at den venstre halvdelen vil være mindre enn den høyre halvdel, fordi dette skjer med bestå av tre elementer. 

Og så kommer jeg til å si at venstre halvdel av den venstre halvdel av matrisen er bare element fem. Five, som er en enkelt element array, vet vi hvordan vi skal sortere det. Og så five blir sortert. Vi er bare nødt til å erklære det. Det er et enkelt element array. 

Så vi har nå sortert venstre halvdel av venstre half-- eller rettere sagt, har vi sortert venstre halvdel av oransje. Så nå, for å fortsatt komplett den samlede tabellens venstre halvdel, vi trenger å sortere høyre halvdel av den oransje, eller slike ting. Hvordan gjør vi det? Vel, vi har en to element array. Så vi kan sortere venstre halvdel i matrisen, som er to. To er et enkelt element. Så det er sortert etter standard. Da kan vi sortere høyre halvdel av den del av matrisen, at en. Det er liksom som standard. 

Dette er nå første gang vi har nådd et flette trinn. Vi har gjennomført, selv om vi nå slags nestet down-- og det er liksom den vanskelige Saken med rekursjon er, du trenger for å holde hodet om hvor vi er. Så vi har liksom venstre halvparten av den oransje partiet. 

Og nå er vi i midten av sortering den høyre halvdel av den oransje partiet. Og i denne prosessen, er vi nå i ferd med å bli på trinnet, fusjonere de to halvdelene sammen. Når vi ser på de to halvdelene av tabellen, ser vi to og en. Hvilket element er mindre? En. 

Så hvilket element er mindre? Vel, det er to eller ingenting. Så det er to. Så nå, bare for å igjen ramme hvor vi er i sammenheng, Vi har sortert venstre halvdel av oransje og den høyre halvdel av opprinnelsen. Jeg vet jeg har endret fargene igjen, men det er der vi var. Og grunnen til at jeg gjorde dette er fordi denne prosessen er kommer til å holde det gående, itera ned. Vi har sortert venstre halvparten av det tidligere orange og den høyre halvparten av det tidligere orange. 

Nå trenger vi å fusjonere de to halvdeler sammen også. Det er det trinnet vi er på. Så vi vurdere alle elementer som nå er grønn, den venstre halvdel av den opprinnelige matrisen. Og vi slå sammen de ved hjelp av den samme prosessen vi gjorde for å slå sammen to og en bare et øyeblikk siden. 

Venstre halvdel, den minste element på den venstre halvdelen er fem. Det minste elementet på høyre halvdel er en. Hvilken av disse er mindre? En. 

Det minste elementet på den venstre halvdelen er fem. Det minste elementet på høyre halvdel er to. Hva er det minste? Two. Og så til slutt fem og ingenting, kan vi si fem. 

OK, så store bildet, la oss ta en pause for en andre og finne ut hvor vi er. Hvis vi startet fra helt i begynnelsen, vi har nå fullført for den generelle matrisen bare ett trinn av pseudokode her. Vi har sortert venstre halvdel av tabellen. 

Husk at den opprinnelige For var fem, to, en. Ved å gå gjennom denne prosessen og hekkende ned og gjenta, fortsetter å bryte problemet ned i mindre og mindre deler, Vi har nå fullført trinn en av pseudokode for hele start matrisen. Vi har sortert sin venstre halvdel. 

Så nå kan vi fryse der. Og nå la oss sortere riktig halvparten av den opprinnelige matrisen. Og vi kommer til å gjøre det ved å gå gjennom den samme iterativ Prosessen med å bryte ned ting og deretter flette dem sammen. 

Så den venstre halvdel av rød, eller venstre halvdel av den høyre halvparten av den opprinnelige array, kommer jeg til å si er tre. Igjen, jeg er å være konsekvent her. Hvis du har en merkelig antall elementer, det spiller ingen rolle om du gjøre det igjen ett mindre eller den rette mindre. 

Det som betyr noe er at når du opplever dette problemet i å gjennomføre en sammenslåing, må du være konsekvent. Du enten alltid trenger å ta til venstre side mindre eller alltid trenger å gjøre høyre side mindre. Her har jeg valgt å alltid gjøre venstre side mindre da min array, eller min deloppstilling, er av et odde størrelse. 

Tre er et enkelt element, og så er det sortert. Vi drar nytte av at antakelsen gjennom hele prosessen så langt. Så nå la oss sortere riktig halvparten av den høyre halvdel, eller høyre halvdel av rødt. 

Igjen, vi trenger å dele dette ned. Dette er ikke et enkelt element array. Vi kan ikke erklære det sortert. Og så først skal vi til å sortere den venstre halvdelen. 

Den venstre halvdel er et enkelt element, så det er liksom som standard. Så skal vi til å sortere riktig halvparten, noe som er et enkelt element. Den er sortert etter standard. Og nå, vi kan slå sammen de to sammen. Fire er mindre, og deretter seks er mindre. 

Igjen, hva har vi gjort på dette punktet? Vi har sortert venstre halvparten av den høyre halvdel. Eller gå tilbake til den opprinnelige farger som var der, vi har sortert venstre halvparten av det mykere rødt. Det var opprinnelig en mørk murstein rød og nå er det en mykere rød, eller det var en mykere rødt. 

Og så har vi sortert høyre halvdel av mykere rødt. Nå, vel, de er grønne igjen, bare fordi vi går gjennom en prosess. Og vi må gjenta dette igjen og igjen. 

Så nå kan vi slå sammen de to halvdeler sammen. Og det er det vi gjør her. Så den svarte linjen bare delt den venstre halvdelen og høyre halvdel av denne typen delen. 

Vi sammenligner den minste verdien på venstre side av array-- eller unnskylde meg, den minste Verdien av den venstre halvdel til den minste verdi av den rette halvparten og finner ut at tre er mindre. Og nå litt av en optimalisering, ikke sant? Det er faktisk ingenting igjen på venstre side. 

Det er ingenting igjen på venstre side, så vi kan effektivt bare move-- vi kan erklære resten av det faktisk sortert og bare tack det på, fordi det er ingenting annet å sammenligne mot. Og vi vet at høyre side på høyre side er sortert. 

OK, så nå la oss fryse igjen og finne ut hvor vi er i historien. I den generelle array, hva har vi oppnådd? Vi har faktisk utrette trinn nå en og trinn to. Vi sortert venstre halvdel, og vi sortert høyre halvdel. 

Så nå, er for oss alt som gjenstår å slå sammen de to halvdelene sammen. Så sammenligner vi den laveste verdsatt element i hver halvdel av matrisen igjen og fortsette. Det ene er mindre enn tre, så man går. 

To er mindre enn tre, så to går. Tre er mindre enn 5, så tre går. Fire er mindre enn 5, så fire går. Da fem er mindre enn seks, og seks er alt som gjenstår. 

Nå, jeg vet, det var mange av trinnene. Og vi har ikke mye minne i kjølvannet. Og det er det de grå rutene er. Og det sannsynligvis føltes som det tok mye lenger enn innsetting sortere, boble sortere, eller valg liksom. 

Men faktisk, fordi en Mange av disse prosessene Det skjer på samme tid-- som er noe vi vil, igjen, snakke om når vi snakker om rekursjon i en fremtidig video-- denne algoritmen faktisk klart er fundamentalt annerledes enn noe vi har sett før men er også betydelig mer effektiv. 

Hvorfor det? Vel, i verste case scenario, har vi å splitte n elementer opp og deretter rekombinere dem. Men når vi rekombinerer dem, hva vi gjør er i utgangspunktet doble størrelsen av de mindre matriser. Vi har en haug av ett element arrays at vi effektivt kombinere i to element arrays. Og så tar vi dem to element arrays og kombinere dem sammen til fire element arrays, og så videre, og så videre, og så videre, helt til vi ha en enkelt n elementsatsen. 

Men hvor mange doblinger tar det å komme til n? Tenk tilbake til telefonboken eksempel. Hvor mange ganger må vi rive telefonboken i to, hvor mange flere ganger må vi rive telefonboken i to, hvis størrelsen på telefonboken doblet? Det er bare en, ikke sant? 

Så det er en slags logaritmisk element her. Men vi har også fortsatt til minst se på alle de n elementene. Så i verste fall fusjonere slags kjører i n log n. Vi må se på alle av de n elementene og vi må kombinere dem sammen i log n sett med trinn. I beste fall matrisen er perfekt sortert. Det er flott. Men basert på algoritmen vi har her, vi har fortsatt å splitte og rekombinerer. Selv om det i dette tilfellet rekombinerende er slags ineffektiv. Det er ikke nødvendig. Men vi fortsatt gå gjennom hele prosessen uansett. 

Så i beste fall og i verste fall denne algoritmen kjører i n log n gang. Merge sort er definitivt litt mer komplisert enn de andre hovedsorteringsalgoritmer vi har snakket om CS50 men er vesentlig kraftigere. 

Og så hvis du skulle finne anledning til å trenge det eller å bruke den til å sortere en store datasett, får hodet rundt ideen om rekursjon kommer til å være veldig kraftig. Og det kommer til å gjøre programmer egentlig mye mer effektiv bruker fusjonere slags versus noe annet. Jeg er Doug Lloyd. Dette er CS50.