[Musiikkia] 

DOUG Lloyd: OK, joten yhdistäminen lajitella on vielä toinen algoritmi että voimme käyttää selvittää elementtejä jono. Mutta kuten näemme, se sai hyvin perustavanlaatuinen ero valinnasta lajitella, kupla lajitella, ja lisäyslajittelun jotka tekevät siitä oikeastaan ​​aika fiksu. 

Perusajatuksena yhdistämisen lajitella on lajitella pienempi paneelit ja sitten yhdistää ne taulukot yhdessä, tai yhdistää them-- joten name-- sisään lajitellut järjestyksessä. Että sulautuvat eräänlainen tekee tämä on hyödyntämällä työkalu nimeltään rekursio, joka on mitä aiomme puhua pian, mutta emme ole oikeastaan ​​puhuneet vielä. 

Tässä perusajatus yhdistämisen lajitella. Järjestellä vasemmalla puolella array, olettaen, että n on suurempi kuin 1. Ja mitä tarkoitan kun sanon olettaen, että n on suurempi kuin 1 on, Mielestäni voimme olla samaa mieltä, että jos jono vain koostuu yhdestä elementin, se on järjestetty. Emme oikeastaan ​​tarvitse tehdä mitään sille. Voimme vain julistaa, että se voidaan lajitella. Se on vain yksi tekijä. 

Niin pseudokoodissa, jälleen, on lajitella vasen puoli array, sitten lajitella oikea puoli jono, sitten yhdistää puolikkaat yhteen. Nyt jo saatat olla ajattelu, se tavallaan vain kuulostaa olet lykännyt the-- et oikeastaan ​​tee mitään. Sanot järjestellä vasen puolet, lajitella oikea puoli, mutta mitä et kerro minut teet sen. 

Mutta muista, että niin kauan kuin array on yksi elementti, voimme julistaa, että se lajitellaan. Sitten voimme vain yhdistää ne yhteen. Ja se on todella perusajatus yhdistämisen lajitella, on murtaa se alas niin, että teidän paneelit ovat koko yksi. Ja sitten rakentaa sieltä. 

Merge sort on ehdottomasti monimutkainen algoritmi. Ja se on myös hieman monimutkainen visualisoida. Joten toivottavasti, visualisointi, että olen on täällä auttaa sinua seurata pitkin. Ja minä yritän parhaani mukaan kertoa asioita ja eteenpäin tätä hieman enemmän hitaasti kuin toisilla vain toivottavasti saa pään ympäri ideoista yhdistämisen lajitella. 

Joten meillä on sama joukko kuin muut lajittelualgoritmi videoita jos olet nähnyt them-- kuusi alkiotaulukon. Ja meidän pseudokoodilla koodi tässä eräänlainen vasen puoli, lajitella oikea puoli, yhdistää puolikkaat yhteen. Joten ottaa tämän hyvin tumma tiilenpunainen array ja lajitella vasemmalle puolet. 

Joten toistaiseksi aiomme sivuuttaa kamaa oikealla. Se on olemassa, mutta olemme ei siinä vaiheessa vielä. Emme ole lajitella oikealla puolella jono. Me olemme tavallaan vasemmalla puolet jono. Ja vain vuoksi olemisen hieman kirkas, joten en voi viitata mitä askel me olemme, Aion vaihtaa väri Tästä oranssiksi. Nyt olemme yhä puhumme sama vasen puolet alkuperäisestä array. Mutta toivon, että voidessaan viittaavat värit eri kohteita, se tulee tehdä hieman enemmän selvää, mitä täällä tapahtuu. 

OK, joten nyt meillä on kolme alkiotaulukko. Miten lajitella vasen puoli tämän array, joka on vielä tässä vaiheessa? Yritämme lajitella vasemmalle puolet tiilenpunainen array-- vasen puoli, jonka Olen nyt oranssinvärinen. 

No, voisimme yrittää Toistan tämän prosessin uudelleen. Joten olemme edelleen keskellä yrittää lajitella vasemmalla puolella täyden valikoiman. Vasemmalla puolella array, olen juuri menossa mielivaltaisesti päättää, että vasen puoli on pienempi kuin oikea puoli, koska tämä tapahtuu koostuvat kolmesta osasta. 

Ja niin aion sanoa, että vasen puoli vasen puoli array on vain osa viisi. Viisi, että yksi elementti array, tiedämme, miten lajitella. Ja niin viisi lajitellaan. Olemme juuri menossa toteamaan. Se on yksi alkiotaulukon. 

Joten olemme nyt lajiteltu vasen puoli vasemman half-- tai pikemminkin olemme lajiteltu vasen puoli oranssi. Joten nyt, jotta vielä valmis yleinen array vasen puoli, meidän täytyy lajitella oikea puoli oranssi, tai tätä kamaa. Miten me sen teemme? No, meillä on kaksi alkiotaulukon. Joten voimme lajitella vasen puoli array, joka on kaksi. Kaksi on yksi elementti. Joten se on lajiteltu oletuksena. Sitten voimme lajitella oikea puoli sen osan array, yksi. Se on tavallaan oletuksena. 

Tämä on nyt ensimmäistä kertaa olemme saavuttaneet yhdistämisen askel. Olemme saattaneet, vaikka olemme nyt sellainen sisäkkäisiä down-- ja se on tavallaan hankala juttu rekursio on, sinun täytyy pitää suunnata noin missä olemme. Joten olemme tavallaan vasemman puolet oranssi osan. 

Ja nyt, olemme keskellä lajittelu oikea puoli oranssi osan. Ja tässä prosessissa, olemme nyt noin olla askel, yhdistää puolikkaat yhteen. Kun katsomme puolikkaat array, näemme kaksi ja yksi. Joka elementti on pienempi? Yksi. 

Sitten joka elementti on pienempi? No, se on kaksi tai ei mitään. Joten se on kaksi. Joten nyt, vain jälleen kehystää missä olemme yhteydessä, olemme lajiteltu vasemmalla puolella oranssi ja oikea puoli alkuperää. Tiedän Olen muuttanut värit jälleen, mutta siitähän olimme. Ja syy Tein on, koska tämä prosessi on menossa pitämään menossa, iteroimalla alas. Olemme järjestetty vasen puolet entisen oranssi ja oikea puoli entisen oranssi. 

Nyt meidän täytyy yhdistää nämä puolikkaat yhdessä liikaa. Se on askel me olemme. Joten pidämme kaikki elementtejä, jotka ovat nyt vihreä, vasen puolet alkuperäisestä array. Ja me yhdistää ne käyttäen samaa prosessia teimme yhdistämällä kaksi ja yksi vain hetki sitten. 

Vasen puoli, pienin elementti vasemmalla puolella on viisi. Pienin elementti oikea puoli on yksi. Mikä näistä on pienempi? Yksi. 

Pienin elementti vasen puoli on viisi. Pienin elementti oikea puoli on kaksi. Mikä on pienin? Kaksi. Ja sitten lopuksi viisi ja mitään, voimme sanoa viisi. 

OK, joten iso kuva, katsotaanpa taukoa toisen ja selvittää, missä olemme. Jos me alkoi alusta, me on nyt valmistunut yleinen array vain yksi askel pseudokoodin koodi tähän. Olemme lajiteltu vasemmalla puolella jono. 

Muista, että alkuperäinen järjestys oli viisi, kaksi, yksi. Käymällä läpi tämän prosessin ja pesivät alas ja toistetaan, edelleen rikkoa ongelma pienempiin ja pienempiin osiin, olemme nyt valmistunut vaihe yksi pseudokoodina koko alkaa jono. Olemme lajiteltu sen vasen puoli. 

Joten Nyt jäädyttää siellä. Ja Nyt lajitella oikealla puolet alkuperäisestä array. Ja aiomme tehdä, että läpi samaa iteratiivista prosessi rikkoa asioita alas ja sitten yhdistämällä ne yhteen. 

Joten vasemmalla puolella punainen, tai vasen puoli oikeuden puolet alkuperäisestä array, aion sanoa on kolme. Jälleen olen johdonmukainen täällä. Jos sinulla on pariton useita tekijöitä, se ei ole oikeastaan ​​väliä, onko teet vasemmalle yksi pienempi tai oikea pienempi. 

Tärkeintä on, että aina kun tämä ongelma ilmenee suorittamisessa yhdistämisen, sinun täytyy olla johdonmukainen. Joko aina tarvitse tehdä vasemmalla puolella pienempi tai aina tarvitse tehdä oikealla puolella pienempi. Täällä, olen päättänyt aina tehdä vasemmalla puolella pienempi kun minun array, tai minun aliryhmälle, on pariton koon. 

Kolme on yksi elementti, ja niin se lajitellaan. Olemme velkarahalla että oletus koko meidän koko prosessin toistaiseksi. Joten Nyt lajitella oikealla puolet oikea puoli, tai oikealla puolella punainen. 

Jälleen meidän täytyy jakaa tämän alas. Tämä ei ole yksittäinen tekijä array. Emme voi julistaa sen lajiteltu. Ja niin ensimmäinen aiomme lajitella vasen puoli. 

Vasen puoli on yksittäinen tekijä, joten se on tavallaan oletuksena. Sitten aiomme lajitella oikealle puoli, joka on yksi elementti. Se lajiteltu oletuksena. Ja nyt, voimme yhdistää nämä kaksi yhdessä. Neljä on pienempi, ja sitten kuusi on pienempi. 

Jälleen mitä olemme tehneet tässä vaiheessa? Olemme järjestetty vasen puolet oikea puoli. Tai menee takaisin alkuperäiseen värit, jotka olivat siellä, olemme lajiteltu vasen puolet pehmeämpi punainen. Se oli alun perin tumma tiili punainen ja nyt se on pehmeämpi punainen, tai se oli pehmeämpi punainen. 

Ja sitten olemme lajiteltu oikea puoli pehmeämpi punainen. Nyt, hyvin, he ovat vihreä jälleen, vain koska olemme menossa läpi prosessin. Ja meidän on toistettava tämä uudestaan ​​ja uudestaan. 

Joten nyt voimme yhdistää nämä puolikkaat yhteen. Ja sitähän me teemme täällä. Niin musta viiva vain jaettu vasen puoli ja oikea puoli tämmöinen osan. 

Vertaamme pienin arvo vasemmalla puolella array-- tai anteeksi, pienin arvo vasen puoli pienintä arvoa oikea puoli ja huomaat, että kolme on pienempi. Ja nyt vähän optimoinnin, eikö? Ei oikeastaan ​​mitään vasemmalle vasemmalla puolella. 

Ei ole mitään jäljellä vasemmalla puolella, joten voimme tehokkaasti vain move-- voimme julistaa loput se on todella lajiteltu ja vain tack se on, koska ei ole mitään muu vertailla vastaan. Ja me tiedämme, että oikea puoli oikean puolen lajitellaan. 

OK, joten nyt katsotaanpa jäädyttää uudelleen ja selvittää missä olemme tarina. Kun yleinen array, mitä olemme aikaan? Olemme todella saavuttaa nyt vaiheet yksi ja toinen vaihe. Olemme järjestetty vasen puoli, ja me lajitellaan oikea puoli. 

Joten nyt, jäljellä on meille yhdistää nämä kaksi puolikasta yhteen. Joten vertaamme alin arvostettu elementti kummankin puoliskon array puolestaan ​​ja edetä. Yksi on vähemmän kuin kolme, niin mennään. 

Kaksi on vähemmän kuin kolme, joten kaksi menee. Kolme on alle 5, niin kolme menee. Neljä on alle 5, niin neljä menee. Sitten viisi on alle kuusi, ja kuusi on kaikki pysyy. 

Nyt tiedän, että oli runsaasti portaita. Ja olemme jätti paljon muistin meidän vanavedessä. Ja sitähän harmaita neliöt ovat. Ja se luultavasti tuntui että otti paljon kauemmin kuin lisäyslajittelun, kupla lajitella, tai valinta lajitella. 

Mutta todellisuudessa, koska Monet näistä prosesseista tapahtuu samaan time-- joka on jotain käymme, jälleen, puhua, kun puhumme rekursio tulevassa video-- tämä algoritmi todella selvästi on pohjimmiltaan eri kuin mitään olemme nähneet aiemmin mutta on myös huomattavasti tehokkaampi. 

Miksi näin? No, pahimmassa tapauksessa, meillä on jakaa n elementtiä ylös ja sitten recombine niitä. Mutta kun me recombine heille, mitä teemme on periaatteessa kaksinkertaistaa koko pienempi paneelit. Meillä on joukko yhden elementin paneelit että me tehokkaasti yhdistää kahteen elementtiin taulukot. Ja sitten otamme ne kaksi elementin taulukot ja yhdistellä niitä neljä elementti paneelit, ja niin edelleen, ja niin edelleen, ja niin edelleen, kunnes on yksi n alkiotaulukon. 

Mutta kuinka moni kahdentumisen kestää päästä n? Muistelen puhelinluetteloon esimerkki. Kuinka monta kertaa meidän täytyy repiä puhelinluettelon kahtia, kuinka paljon enemmän kertaa meillä on repiä puhelinluettelo kahtia, jos koko puhelinluettelon kaksinkertaistunut? On vain yksi, oikea? 

Joten ei jonkinlainen logaritminen elementti täällä. Mutta meillä on myös vielä ainakin tarkastella kaikkia n alkiota. Joten pahimmassa tapauksessa, yhdistää lajitella toimii n log n. Meidän on tarkasteltava kaikki n elementtejä, ja meidän on yhdistää ne yhdessä log n sarjaa vaiheita. Parhaassa tapauksessa, array on täydellisesti lajitellaan. Sepä hienoa. Vaan perustuu algoritmiin olemme täällä, meillä on vielä jakaa ja yhdistää. Vaikka tässä tapauksessa, yhdistimeen on tavallaan tehoton. Sitä ei tarvita. Mutta me silti mennä läpi koko prosessin muutenkin. 

Joten parhaassa tapauksessa ja pahimmassa tapauksessa, tämä algoritmi toimii n log n aikaa. Merge sort on ehdottomasti hieman hankalampaa kuin muut tärkeimmät lajittelualgoritmeja olemme puhuneet CS50 mutta on huomattavasti tehokkaampi. 

Ja joten jos koskaan löytää tilaisuus tarvitse sitä tai käyttää sitä lajitella suuri tietokokonaisuutta, saada pään ympärillä ajatus rekursio tulee olemaan todella voimakas. Ja se tulee tehdä ohjelmat todella paljon tehokkaampaa käyttäen yhdistää lajitella vastaan ​​mitään muuta. Olen Doug Lloyd. Tämä on CS50.