[Speel van musiek] 

DOUG LLOYD: OK, so 'n samesmelting soort is nog 'n algoritme wat ons kan gebruik om uit te sorteer die elemente van 'n skikking. Maar soos ons sal sien, is dit 'n baie fundamentele verskil van seleksie soort, borrel soort, en voeg soort wat maak dit regtig mooi slim. 

Die basiese idee agter merge sorteer is om kleiner skikkings sorteer en kombineer dan diegene skikkings saam te smelt of them-- vandaar die name-- in gesorteerde volgorde. Die manier waarop saamsmelt soort doen dit is deur gebruik te maak 'n instrument genoem rekursie, en dit is wat ons gaan om te praat oor gou, maar ons het nie regtig gepraat oor nie. 

Hier is die basiese idee agter merge soort. Sorteer die linker helfte van die skikking, veronderstelling N groter as 1. En wat ek bedoel as ek sê veronderstelling N groter as 1 is, Ek dink ons ​​kan saamstem dat indien 'n skikking net bestaan ​​uit 'n enkele element, dit is gesorteer. Ons het nie eintlik nodig om iets te doen om dit te. Ons kan net verklaar dat dit word gesorteer. Dit is net 'n enkele element. 

So die pseudokode, weer, is sorteer die linker helfte van die skikking, dan sorteer die regter helfte van die skikking, dan saam te smelt die twee helftes saam. Nou, al wat jy kan wees dink, is dit soort van net klink soos jy om af the-- jy nie eintlik enigiets doen. Jy sê sorteer links helfte, sorteer die regter helfte, Maar jy is nie vertel my hoe jy doen dit. 

Maar onthou dat so lank as wat 'n skikking is 'n enkele element, kan ons dit verklaar gesorteer. Dan kan ons net kombineer hulle saam. En dit is eintlik die fundamentele idee agter merge soort, is om dit af te breek sodat jou skikkings is van die grootte een. En dan moet jy weer op te bou van daar af. 

Merge soort is beslis 'n ingewikkelde algoritme. En dit is ook 'n bietjie ingewikkeld om te visualiseer. So hopelik die visualisering dat ek hier sal help jy volg saam. En ek sal my bes probeer om dinge te vertel en gaan deur middel van hierdie 'n bietjie meer stadiger as die ander kinders net om hopelik kry jou kop rondom die idees agter merge soort. 

So ons het dieselfde verskeidenheid as die ander sorteer algoritme videos As jy gesien het them-- 'n ses element skikking. En ons pseudokode kode hier is 'n soort die linker helfte, sorteer die regter helfte, saamsmelt die twee helftes saam. So laat neem hierdie baie donker baksteenrooi skikking en sorteer die linkerkant helfte van dit. 

So vir die oomblik, ons gaan om die dinge op die regte ignoreer. Dit is daar, maar ons is nie nog daardie stap. Ons is nie op die soort regter helfte van die skikking. Ons is op sorteer links helfte van die skikking. En net ter wille dat dit 'n bietjie meer duidelik, sodat ek kan verwys na wat stap ons op, Ek gaan die skakel kleur van hierdie stel na oranje. Nou, ons is nog steeds praat oor die dieselfde links die helfte van die oorspronklike skikking. Maar ek hoop dat deur dit kan verwys na die kleure van die verskillende items, dit sal dit 'n bietjie meer te maak duidelik wat gaan hier aan. 

OK, so nou het ons 'n drie element skikking. Hoe weet ons sorteer die linker helfte van hierdie skikking, wat nog steeds hierdie stap? Ons probeer om die linker sorteer helfte van die baksteen rooi array-- die linker helfte van wat Ek het nou gekleurde oranje. 

Wel, kan ons probeer herhaal hierdie proses. So ons is nog steeds in die middel van probeer om te sorteer die linker helfte van die volle reeks. Die linker helfte van die skikking, is ek net gaan om arbitrêr besluit dat die linker helfte kleiner as die regter helfte sal wees, want dit gebeur met bestaan ​​uit drie elemente. 

En so ek gaan om te sê dat die linkerhelfte van die linker helfte van die reeks is net die element vyf. Vyf, wat 'n enkele element skikking, ons weet hoe om dit te sorteer. En so vyf gesorteer. Ons is net gaan om te verklaar dat. Dit is 'n enkele element skikking. 

Dus het ons nou gesorteer die linkerhelfte van die linker half-- of eerder, ons het gesorteer die links die helfte van die oranje. So nou, ten einde steeds volledige links die helfte van die algehele array se ons nodig het om die regter helfte sorteer van die oranje, of hierdie dinge. Hoe kan ons dit doen? Wel, ons het 'n twee element skikking. So kan ons die weg helfte sorteer van die skikking, wat twee. Twee is 'n enkele element. So dit gesorteer is by verstek. Dan kan ons die regter helfte sorteer van daardie gedeelte van die skikking, die een. Dit is soort van by verstek. 

Dit is nou vir die eerste keer Ons het 'n merge stap bereik. Ons voltooi het, hoewel ons nou soort van geneste down-- en dit is soort van die moeilike ding met rekursie is, wat jy nodig het om jou te hou kop oor waar ons is. Dus het ons soort van links helfte van die oranje gedeelte. 

En nou, ons is in die middel van die sortering die regter helfte van die oranje gedeelte. En in die proses, ons is nou tot op die stap, saamsmelt die twee helftes saam. As ons kyk na die twee helftes van die skikking, sien ons twee en een. Watter element is kleiner? Een. 

Dan watter element is kleiner? Wel, dit is twee of niks. So dit is twee. So nou, net om weer te raam waar ons is in konteks, ons het gesorteer die links die helfte van die oranje en die regter helfte van die oorsprong. Ek weet ek het die kleure verander weer, maar dit is waar ons was. En die rede waarom ek dit gedoen het is omdat hierdie proses is gaan om aan te hou, iterating af. Ons het die linker gesorteer helfte van die voormalige oranje en die regter helfte van die voormalige oranje. 

Nou moet ons diegene saamsmelt twee helftes saam ook. Dit is die stap ons op. So ons kyk na al die elemente wat nou groen, die linker helfte van die oorspronklike skikking. En ons saamsmelt diegene gebruik dieselfde proses ons gedoen het vir die samesmelting van twee en een net 'n oomblik gelede. 

Die linker helfte, die kleinste element op die linker helfte is vyf. Die kleinste element op die regter helfte is een. Watter een van dié is kleiner? Een. 

Die kleinste element op die linker helfte is vyf. Die kleinste element op die regter helfte is twee. Wat is die kleinste? Twee. En dan laastens vyf en niks kan ons sê vyf. 

OK, so groot prentjie, laat neem 'n breek vir 'n tweede en uit te vind waar ons is. As ons begin van die begin af, ons het nou voltooi die algehele array net een stap van die pseudokode kode hier. Ons het die gesorteer linkerhelfte van die skikking. 

Onthou dat die oorspronklike Om was vyf, twee, een. Deur te gaan deur die proses en nes af en herhaal, voortgaan om die probleem te breek af in kleiner en kleiner dele, ons het nou voltooi Stap een van die pseudokode vir die hele beginspan skikking. Ons het sy linker helfte gesorteer. 

So nou, laat ons daar vries. En nou, laat se sorteer die regte die helfte van die oorspronklike skikking. En ons gaan om dit te doen deur gaan deur dieselfde iteratiewe proses van die breek dinge af en dan saamsmelt hulle saam. 

So die linker helfte van die rooi, of die linker helfte van die reg helfte van die oorspronklike skikking, ek gaan om te sê, is die drie. Weereens, ek hier is konsekwent. As jy 'n vreemde aantal elemente, is dit maak nie regtig saak of jy links een kleiner te maak of die regte een kleiner. 

Wat belangrik is, is dat wanneer jy teëkom hierdie probleem in die uitvoering van 'n saamsmelt, moet jy konsekwent te wees. Jy óf altyd nodig om maak 'n linkerkant kleiner of altyd nodig om te maak die regterkant kleiner. Hier het ek gekies om altyd maak die linkerkant kleiner toe my skikking, of my sub-skikking, is van 'n vreemde grootte. 

Drie is 'n enkele element, en so is dit gesorteer. Ons het hierdie aanname aged ons hele proses so ver. So nou, laat ons sorteer die regte helfte van die regter helfte, of die regter helfte van die rooi. 

Weereens, moet ons dit verdeel af. Dit is nie 'n enkele element skikking. Ons kan nie verkondig nie gesorteer. En so die eerste, ons gaan aan die linkerkant half sorteer. 

Die linker helfte is 'n enkele element, so dit is soort van by verstek. Dan gaan ons die regte soort helfte, wat is 'n enkele element. Dit is gesorteer by verstek. En nou, ons kan die twee saam te smelt. Vier is kleiner, en dan ses kleiner is. 

Weereens, wat het ons gedoen op hierdie punt? Ons het die linker gesorteer helfte van die regter helfte. Of gaan terug na die oorspronklike kleure wat daar was, ons het die linker gesorteer helfte van die sagter rooi. Dit was oorspronklik 'n donker baksteen rooi en nou is dit 'n sagter rooi, of was dit 'n sagter rooi. 

En dan het ons gesorteer die regter helfte van die sagter rooi. Nou, goed, hulle is groen weer, net want ons gaan deur 'n proses. En ons moet herhaal dit oor en oor. 

So nou kan ons saam te smelt diegene twee helftes saam. En dit is wat ons hier doen. So die swart lyn net verdeel die linker helfte en die regter helfte van hierdie soort deel. 

Ons vergelyk die kleinste waarde aan die linkerkant van die array-- of verskoon my, die kleinste waarde van die linker helfte die kleinste waarde van die reg helfte en vind dat drie kleiner is. En nou 'n bietjie van 'n optimalisering, reg? Daar is eintlik niks links op die linkerkant. 

Daar is niks wat oorbly aan die linkerkant, sodat ons kan doeltreffend net move-- kan ons verklaar die res van dit is eintlik gesorteer en net ryg dit op, want daar is niks anders vergelyk. En ons weet dat die regterkant van die regterkant gesorteer. 

OK, so nou kom ons weer vries en uit te vind waar ons is in die storie. In die algehele skikking, wat het ons bereik? Ons het eintlik bereik nou gee een en stap twee. Ons gesorteer links helfte, en Ons gesorteer die regter helfte. 

So nou, al wat oorbly is vir ons om die twee helftes saam te smelt. So ons vergelyk met die laagste gewaardeer element van elke helfte van die skikking op sy beurt en voort te gaan. Een daarvan is minder as drie, so een gaan. 

Twee is minder as drie, so twee gaan. Drie is minder as 5, so drie gaan. Vier is minder as 5, so vier gaan. Dan is vyf minder as ses, en ses is al wat oorbly. 

Nou, ek weet, dit was 'n baie stappe. En ons het 'n baie gelaat geheue in ons wakker. En dit is wat die grys vierkante is. En dit is waarskynlik so gevoel het 'n baie langer as invoeging soort, borrel soort, of seleksie soort. 

Maar eintlik, want 'n Baie van hierdie prosesse gebeur op dieselfde time-- dit is iets wat ons sal weer, praat oor wanneer ons praat oor rekursie in 'n toekomstige video-- hierdie algoritme eintlik duidelik is fundamenteel anders as enigiets ons vantevore gesien maar is ook aansienlik meer doeltreffend. 

Hoekom is dit? Wel, in die ergste geval scenario, ons het om n elemente verdeel en dan herkombineer hulle. Maar toe ons herkombineer hulle wat ons doen is basies die verdubbeling van die grootte van die kleiner skikkings. Ons het 'n klomp van die een element skikkings dat ons effektief kombineer in twee element skikkings. En dan neem ons daardie twee skikkings element en kombineer hulle saam in vier element skikkings, en so aan, en so aan, en so aan, totdat ons 'n enkele N element skikking. 

Maar hoeveel verdubbelingen neem dit om n te kry? Dink terug aan die telefoon boek voorbeeld. Hoeveel keer het ons om te skeur die telefoon boek in die helfte, hoeveel meer keer doen ons die telefoon boek skeur in die helfte, as die grootte van die telefoon boek verdubbel? Daar is net een, reg? 

So is daar 'n soort van logaritmiese element hier. Maar ons het ook nog moet ten minste kyk na al die elemente N. So in die ergste geval scenario, saamsmelt soort loop in n log n. Ons het om te kyk na al die elemente N, en ons het om hulle te kombineer saam in log N stelle stappe. In die beste geval, die skikking is perfek gesorteer. Dit is 'n groot. Maar op grond van die algoritme wat ons hier, ons het nog te verdeel en verbind. Hoewel in hierdie geval, die recombining is soort van ondoeltreffend. Dit is nie nodig nie. Maar ons het nog gaan deur die hele proses in elk geval. 

So in die beste geval en in die ergste geval, hierdie algoritme loop in n log N tyd. Merge soort is beslis 'n bietjie moeiliker as die ander belangrikste sorteringsalgoritmes Ons het gepraat oor CS50, maar is aansienlik meer kragtig. 

En so as jy ooit vind geleentheid om dit nodig of om dit te gebruik om 'n soort groot data stel, om jou kop rondom die idee van rekursie gaan werklik kragtig te wees. En dit gaan om jou programme regtig veel meer doeltreffend gebruik van saamsmelt soort versus enigiets anders. Ek is Doug Lloyd. Dit is CS50.