[REPRODUCCIÓ DE MÚSICA] 

DOUG LLOYD: OK, pel que una fusió espècie és un altre algoritme que podem utilitzar per solucionar els elements d'una matriu. Però com veurem, té un diferència molt fonamental des de la selecció del tipus, bombolla ordenar i ordenació per inserció que fan que sigui realment molt intel·ligent. 

La idea bàsica darrere de la fusió classe és per ordenar arrays més petits i després combinar els arrays junts, o fusionar ells-- d'aquí el nom-- en forma ordenada. La forma en què es fonen espècie fa això és mitjançant l'aprofitament d'una eina crida recursivitat, que és el que estarem parlant de sobte, però en realitat no hem parlat encara. 

Aquesta és la idea bàsica darrere de mescla tipus. Ordeneu la meitat esquerra de la matriu, suposant que n és més gran que 1. I el que vull dir quan dic suposant que n és més gran que 1, és a dir, Crec que podem estar d'acord que si una matriu només es compon d'un únic element, es va arreglar. En realitat no necessitem de fer res per a ell. Només podem declarar a classificar. No és més que un sol element. 

Així que el pseudocodi, de nou, és ordenar la meitat esquerra de la matriu, a continuació, ordenar la meitat dreta de la matriu, després fusionar les dues meitats. Ara, ja que podria ser pensar, és com que acaba de sona com vostè està posant fora ell-- vostè no està realment fent res. Estàs dient que ordenar l'esquerra mitjà, més o menys la meitat dreta, però no s'està dient mi com ho estàs fent. 

Però recordeu que mentre una matriu és un sol element, podem declarar el va arreglar. Llavors només podem combinar-los. I això és en realitat el idea fonamental darrere de combinació de classe, és trencar cap avall perquè les matrius són de talla única. I després torna a generar a partir d'aquí. 

Merge Sort és definitivament un algoritme complicat. I també és una mica complicat de visualitzar. Així que és d'esperar, la visualització que té aquí l'ajudarà a el segueix. I intentaré meu millor esforç per narrar les coses i procedir a través d'això una mica més lentament que els altres només per obtenir espere teu cap al voltant de les idees darrere de mescla tipus. 

Així que tenim la mateixa matriu com la altres vídeos de l'algorisme de classificació ells-- si has vist una matriu de sis elements. I el nostre codi pseudocodi aquí és una espècie la meitat esquerra, ordenar la meitat dreta, fusionar les dues meitats juntes. Així que prenguem aquest maó vermell molt fosc matriu i ordenar el mig que queda d'ella. 

Així que de moment, anem fer cas omís de les coses a la dreta. Hi és, però estem no en aquest pas encara. No estem en la classe mitjana dreta de la matriu. Estem en una espècie de l'esquerra mitjà de la matriu. I només pel bé de ser una mica més clar, així que em puc referir al que el pas que estem en, Vaig a canviar la color d'aquest conjunt de taronja. Ara, encara estem parlant de la mateixa meitat esquerra de la matriu original. Però espero que en ser capaços de referir-se als colors de diversos articles, que va a fer una mica més aclarir el que està passant aquí. 

OK, així que ara tenim una de tres conjunt d'elements. Com ordenar la mitjana esquerra d'aquesta array, que segueix sent aquest pas? Estem tractant d'ordenar l'esquerra mitjà del array-- maó vermell la meitat esquerra dels quals Ara he de color taronja. 

Bé, podríem intentar repetir aquest procés una altra vegada. Així que encara estem en el mitjà de tractar de classificar la meitat esquerra de la matriu completa. La meitat esquerra de la matriu, només vaig per decidir arbitràriament que la meitat esquerra serà menor que la meitat dreta, perquè això li passa a constarà de tres elements. 

I pel que vaig a dir que la mitjana esquerra de la meitat esquerra de la matriu és només l'element de cinc. Cinc, sent un sol element matriu, sabem com arreglar-ho. I així, de cinc s'ordena. Només anem a declarar això. És un sol element de la matriu. 

Així que ara hem van solucionar el meitat esquerra de l'esquerra half-- o més aviat, hem van solucionar el meitat esquerra de la taronja. Així que ara, per tal d'encara completa meitat esquerra de la matriu global, hem de ordenar la meitat dreta de la taronja, o aquestes coses. Com ho fem? Bé, tenim una matriu de dos elements. Així que podem ordenar la mitjana esquerra de la matriu, que és de dos. Dos és un sol element. Així que ha ordenat per defecte. Llavors podem ordenar la meitat dreta d'aquesta porció de la matriu, l'un. Això és una mena de defecte. 

Aquesta és ara la primera vegada hem arribat a una etapa de mescla. Hem completat, encara que ara estem tipus de niat down-- i això és una espècie de la difícil cosa amb la recursivitat és, vostè necessita per mantenir la seva cap sobre on som. Per a això hem espècie de l'esquerra mitjà de la porció de taronja. 

I ara, estem en el mig de la classificació la meitat dreta de la part taronja. I en aquest procés, estem ara a punt d'estar en el pas, fusionar les dues meitats juntes. Quan ens fixem en les dues meitats de la matriu, veiem dos i un. Quin element és menor? Un. 

Llavors quin element és més petit? Bé, és dues o res. Així que és dues. Així que ara, només per emmarcar de nou on som en context, hem ordenat la meitat esquerra de la taronja i la meitat dreta de l'origen. Sé que he canviat els colors de nou, però això és on estàvem. I la raó per la qual va fer això és perquè aquest procés és seguirà endavant, iterant cap avall. Hem van solucionar l'esquerra la meitat de l'antiga taronja i la meitat dreta de l'antiga taronja. 

Ara, hem de combinar els dues meitats també. Aquest és el pas que estem en. Així tenim en compte la totalitat de la elements que ara són de color verd, la meitat esquerra de la matriu original. I ens fusionem els utilitzant el mateix procés ho vam fer per a la fusió de dues i fa un un moment. 

La meitat esquerra, la més petita element en la meitat esquerra és de cinc. El component més petit de la meitat dreta és un. Quin d'ells és més petit? Un. 

El component més petit de la meitat esquerra és de cinc. El component més petit de la meitat dreta és de dos. Quin és el més petit? Dos. I després, finalment, cinc i res, podem dir 5. 

OK, la imatge tan gran, anem a prendre un descans per un segon i esbrinar on som. Si partim de del principi, ens ara s'han completat per la matriu global just un pas del codi pseudocodi aquí. Hem ordenat la mitjana esquerra de la matriu. 

Recordem que l'original ordre era de cinc, dos, un. En passar per aquest procés i niant baix i repetir, contínua per trencar el problema en parts cada vegada més petites, ara hem completat pas un del pseudocodi per a tota la matriu de partida. Hem ordenat la meitat esquerra. 

Així que ara anem a congelar allà. I ara anem a ordenar la dreta la meitat de la matriu original. I anem a fer això per passant pel mateix iteratiu procés de trencar les coses i després fusionar junts. 

Així que la meitat esquerra de la vermell, o la meitat esquerra de la meitat dreta de l'original matriu, que diré és tres. Un cop més, estic sent coherent aquí. Si vostè té un estrany nombre d'elements, en realitat no importa si a prendre el de l'esquerra més petita o el dret d'un menor. 

El que importa és que cada vegada que trobar aquest problema en la realització de una fusió, ha de ser coherent. Vostè bé sempre cal fer una banda esquerre més petit o sempre que hagi de fer el costat dret més petit. Aquí, he optat per sempre fer que la banda esquerra més petit quan el meu matriu, o de la meva sub-matriu, és d'una mida senar. 

Tres és un sol element, i pel que s'ordena. Hem aprofitat aquesta suposició al llarg de tot el nostre procés fins al moment. Així que ara anem a ordenar la dreta la meitat de la meitat dreta, o la meitat dreta de la vermella. 

Un cop més, hem de dividir això. Això no és un únic element de la matriu. No podem declarar el va arreglar. I així, en primer lloc, anem per ordenar la meitat esquerra. 

La meitat esquerra és un sol element, pel que és una espècie de defecte. Llavors anem a ordenar la dreta mitjà, que és un sol element. Està ordenada per defecte. I ara, podem combinar els dos junts. Quatre és més petit, i a continuació, 6 és més petit. 

Un cop més, què hem fet en aquest punt? Hem van solucionar l'esquerra la meitat de la meitat dreta. O tornar a l'original colors que hi eren, hem van solucionar l'esquerra mitjà del vermell més suau. Originalment va ser un maó fosc vermell i ara és un vermell més suau, o que era un vermell més suau. 

I després hem van solucionar el meitat dreta del vermell més suau. Ara, bé, són verds de nou, només perquè anem a través d'un procés. I hem de repetir això una i altra. 

Així que ara podem combinar els dues meitats. I això és el que fem aquí. Així que la línia de negre només dividit a la meitat esquerra i la meitat dreta d'aquesta part de classificació. 

Comparem el valor més petit a la banda esquerra de la array-- o perdó, la més petita valor de la meitat esquerra al valor més petit de la dreta mitjà i trobar que 3 és més petit. I ara una mica d'una optimització, oi? En realitat hi ha res a l'esquerra a la banda esquerra. 

No hi ha res restant a la banda esquerra, perquè puguem de manera eficient simplement move-- podem declarar la resta d'ell és en realitat ordenat i just virar des d'ara, perquè no hi ha res altra cosa que comparar. I sabem que el costat dret del costat dret està ordenada. 

OK, així que ara anem a congelar de nou i esbrinar on som en la història. En la matriu general, ¿Què hem aconseguit? De fet, hem aconseguim ara els passos un i el pas dos. Classifiquem la meitat esquerra, i ens ho van solucionar la meitat dreta. 

Així que ara, tot el que queda és per a nosaltres fusionar aquestes dues meitats. Així comparem el més baix valorat element de cada mitjà de la matriu al seu torn, i procedir. Una d'elles és inferior a tres, de manera que un va. 

Dos és inferior a tres, així que dos va. Tres és inferior a 5, així que tres va. Quatre és inferior a 5, pel que va de quatre. Després de cinc és menys de sis, i 6 és tot el que queda. 

Ara, ho sé, que era un munt de passos. I hem deixat un munt de la memòria en la nostra deixant. I això és el que els quadrats grisos són. I probablement se sentia com que va tenir un molt més temps que l'ordenació per inserció, bombolla espècie, o la selecció de classificació. 

Però, en realitat, ja que un Molts d'aquests processos estan succeint al mateix temps-- que és una cosa que vaig a fer, de nou, parlar quan parlem de recursivitat en un futur vídeo-- aquest algorisme en realitat clarament és fonamentalment diferent a qualsevol cosa hem vist abans però també és significativament més eficient. 

Perquè és això? Bé, en el pitjor dels casos dels casos, tenim dividir n elements dalt i després recombinar ells. Però quan recombinarlo ells, el que estem fent és, bàsicament, la duplicació de la mida de les matrius més petites. Tenim un munt d'un element arrays que efectivament combinar en dos conjunts d'elements. I després prenem els dos conjunts d'elements i combinar-los en quatre conjunts d'elements, i així successivament, i així successivament, i així successivament, fins que tenir una sola n element de la matriu. 

Però, quants duplicacions Què es necessita per arribar al n? Penseu de nou a l'exemple de la guia telefònica. Quantes vegades hem de trencar la guia telefònica al mig, quants més vegades hem de trencar la guia telefònica a la meitat, si la mida de la guia telefònica duplicat? Només n'hi ha una, ¿no? 

Així que hi ha algun tipus de element logarítmica aquí. Però també queda almenys mirar a tots els n elements. Així que en el pitjor dels casos, ordenament per barreja corre n log n. Hem de mirar tots els elements N, i hem de combinar- junts en log n conjunts de passos. En el millor dels casos, la matriu està perfectament ordenades. Això és genial. Però basat en l'algoritme que tenim aquí, encara hem de dividir i recombinar. Encara que en aquest cas, la recombinació és una espècie d'ineficaç. No és necessari. Però encara travessem tot el procés de totes maneres. 

Així, en el millor dels casos i en el pitjor dels casos, aquest algorisme s'executa en n log n temps. Combinar tipus és sens dubte una mica més complicat que els altres algoritmes de classificació principals hem parlat de CS50 però és substancialment més potent. 

I pel que si alguna vegada es troba ocasió per la necessiten o utilitzar-lo per ordenar una gran conjunt de dades, aconseguint seu cap al voltant de la idea de recursivitat serà molt poderosa. I que va a fer el seu programes realment molt més eficient utilitzant fusionar espècie davant res més. Sóc Doug Lloyd. Això és CS50.