[Muziek] 

DOUG LLOYD: OK, dus een fusie soort is nog een ander algoritme die we kunnen gebruiken om uit te zoeken de elementen van een array. Maar zoals we zullen zien, het heeft een zeer fundamenteel verschil uit selectie sorteren, bubble sorteren en insertion sort die het echt mooi slim. 

Het basisidee achter merge sorteren is om kleinere arrays te sorteren en combineer dan die arrays samen, of samenvoegen them-- vandaar de name-- in gesorteerde volgorde. De manier waarop die fuseren soort doet dit is door gebruik te maken van een hulpmiddel genaamd recursie, dat is wat we gaan praten over snel, maar we hebben niet echt gesproken over nog. 

Hier is het basisidee achter merge soort. Sorteer de linkerhelft van de array, uitgaande van n groter is dan 1. En wat ik bedoel als ik zeg uitgaande van n groter dan 1 is, Ik denk dat we het erover eens dat als een array slechts bestaat uit een enkel element, het is opgelost. We niet echt nodig om iets te doen aan het. We kunnen alleen maar verklaren het te sorteren. Het is slechts een enkel element. 

Dus de pseudocode, opnieuw, is sorteren de linkerhelft van de array, vervolgens sorteert de rechter helft van de array, dan samenvoegen van de twee helften aan elkaar. Nu, al u misschien wel denken, het vriendelijk van enkel klinkt alsof je uit te stellen the-- je bent niet echt iets te doen. Je zegt sorteren links helft, sorteert de rechter helft, maar je bent niet vertellen me hoe je het doet het. 

Maar vergeet niet dat, zolang een array is een enkel element, kunnen we verklaren het opgelost. Dan kunnen we net combineren ze samen. En dat is eigenlijk de fundamentele idee achter merge sort, is om het af te breken, zodat uw arrays zijn omvang een. En dan moet je weer op te bouwen vanaf daar. 

Merge sort is zeker een ingewikkeld algoritme. En het is ook een beetje gecompliceerd te visualiseren. Dus hopelijk, de visualisatie die ik hier hebben zal je helpen volgen langs. En ik zal mijn best doen om dingen te vertellen en verder door deze een beetje meer langzamer dan de anderen alleen maar om hopelijk je hoofd rond de ideeën achter merge soort. 

Dus we hebben dezelfde array als de andere sorteer-algoritme videos Als je hebt gezien them-- een zes-element array. En onze pseudocode code hier is een soort de linker helft, sorteren van de rechter helft, samenvoegen van de twee helften aan elkaar. Dus laten we dit zeer donkere baksteen rood array en sorteren van de linker helft van het. 

Dus voor het moment, we gaan om de spullen op de juiste negeren. Het is er, maar we zijn nog niet die stap. We zijn niet bij de soort rechterhelft van de array. We zijn in een soort links de helft van de array. En alleen omwille van een beetje meer duidelijk, dus ik kan verwijzen wat stap we op, Ik ga naar het schakelen kleur van deze set naar oranje. Nu, we zijn nog steeds over de Hetzelfde linkerhelft van de oorspronkelijke array. Maar ik hoop dat door te kunnen verwijzen naar de kleuren van de verschillende items, het zal het een beetje meer te maken duidelijk wat er aan de hand hier. 

OK, dus nu hebben we een drie element array. Hoe kunnen we sorteren de linker helft van dit matrix, die nog steeds deze stap? We proberen links te sorteren de helft van de steenrode array-- de linker helft Ik heb nu oranje gekleurd. 

Nou, we kunnen proberen herhaal dit proces. Dus we zijn nog steeds in de midden van het proberen om te sorteren de linkerhelft van de volledige array. De linkerhelft van het array, ik ben gewoon gaan willekeurig beslissen dat de linkerhelft kleiner is dan de rechterhelft wordt, omdat dit gebeurt bestaan ​​uit drie elementen. 

En dus ik ga om te zeggen dat de linkerhelft van de linkerhelft de array is slechts het element vijf. Vijf, waarbij een enkel element array, we weten hoe we het uitzoeken. En dus vijf wordt gesorteerd. We gaan gewoon om te verklaren dat. Het is een enkel element array. 

Dus we hebben nu naargelang de linkerhelft van de linker half-- of liever gezegd, we hebben naargelang de linkerhelft van het oranje. Dus nu, met het oog op nog compleet linkerhelft de totale array, we nodig hebben om de rechter helft afstand van de oranje of dit spul. Hoe doen we dat? Nou, we hebben een twee-element array. Dus we kunnen de linker helft afstand van de matrix, die twee. Twee een enkel element. Dus het is gesorteerd per default. Dan kunnen we de juiste halve afstand van dat deel van de matrix, het. Dat is een soort van standaard. 

Dit is nu de eerste keer we hebben een fusie stap bereikt. We hebben afgerond, hoewel we nu soort geneste down-- en dat is een soort van de lastige ding met recursie is, je nodig hebt om je te houden hoofd over waar we zijn. Dus we hebben een soort van links de helft van de oranje gedeelte. 

En nu zijn we in het midden van het sorteren de rechterhelft van de oranje gedeelte. En in dat proces zijn we nu op het punt om op de stap, samenvoegen van de twee helften aan elkaar. Wanneer we kijken naar de twee helften van de array, zien we twee en één. Welk element is kleiner? Een. 

Dan welk element kleiner is? Nou, het is twee of niets. Dus het is twee. Dus nu, gewoon om opnieuw inlijsten waar we zijn in context, we hebben naargelang de linkerhelft van de oranje en de rechterhelft van de oorsprong. Ik weet dat ik de kleuren veranderd weer, maar dat is waar we waren. En de reden dat ik dit deed omdat dit proces gaat om door te gaan, iteratie beneden. We hebben de linker naargelang de helft van de voormalige Oranje en de rechterhelft van de voormalige oranje. 

Nu moeten we die fuseren twee helften elkaar ook. Dat is de stap die we nu op. Dus we rekening houden met alle van de elementen die nu groen, de linkerhelft van de oorspronkelijke array. En we samenvoegen die via hetzelfde proces we deden voor het samenvoegen van twee en één slechts een moment geleden. 

De linkerhelft, de kleinste element op de linkerhelft vijf. De kleinste element de rechterhelft één. Welke van die kleiner? Een. 

De kleinste element de linkerhelft vijf. De kleinste element de rechter helft is twee. Wat is de kleinste? Twee. En dan tot slot vijf en niets, kunnen we zeggen vijf. 

OK, dus grote beeld, laten we neem een ​​pauze voor een tweede en erachter te komen waar we zijn. Als we begonnen uit het allereerste begin, we zijn nu ingevuld voor de totale serie net een stap van de pseudo-code hier. We hebben naargelang de linkerhelft van de array. 

Bedenk dat de oorspronkelijke Om vijf, twee, één. Door te gaan door middel van dit proces en nesten omlaag en herhalen, blijft het probleem breken in kleinere en kleinere delen, we nu hebben afgerond stap één van de pseudocode het gehele start array. We hebben haar linker helft opgelost. 

Dus laten we nu daar bevriezen. En laten we nu de juiste afstand de helft van de oorspronkelijke array. En we gaan dat doen door gaan door de dezelfde iteratieve proces van het breken van dingen naar beneden en dan samen te voegen ze samen. 

Dus de linkerhelft van de rood, of de linkerhelft van de rechterhelft van de oorspronkelijke array, ik ga zeggen is drie. Nogmaals, ik ben om hier consequent. Als u een oneven aantal elementen, dat niet echt uit of je links een kleiner te maken of de juiste kleinere. 

Waar het om gaat is dat wanneer je Dit probleem tegenkomen in geleidend een fusie, moet je consequent zijn. Of je altijd nodig hebt om maak een linkerkant kleiner of altijd moet maken rechts kleiner. Hier heb ik gekozen om altijd maken de linkerzijde kleiner toen mijn array, of mijn sub-array, is van een oneven grootte. 

Drie is een enkel element, en dus het wordt gesorteerd. We hebben die veronderstelling leveraged gedurende ons hele proces tot nu toe. Dus laten we nu de juiste afstand de helft van de rechterhelft, of de rechterhelft van de rode. 

Nogmaals, we moeten deze split neer. Dit is geen enkel element array. We kunnen niet verklaren het opgelost. En dus eerst, we gaan aan de linker helft afstand. 

De linkerhelft is een enkel element, dus het is een soort van standaard. Dan gaan we naar de juiste soort half, hetgeen een enkel element. Het is gesorteerd per default. En nu, kunnen we die twee met elkaar fuseren. Vier kleiner, en dan zes is kleiner. 

Nogmaals, wat hebben we gedaan op dit punt? We hebben de linker naargelang de helft van de rechter helft. Of terug te gaan naar de oorspronkelijke kleuren die er waren, we hebben de linker naargelang de helft van de zachtere rood. Het was oorspronkelijk een donkere baksteen rood en nu is het een zachter rood, of het een zachter rood. 

En dan hebben we naargelang de rechterhelft van het zachtere rood. Nu goed, ze zijn weer groen, net want we gaan door middel van een proces. En we moeten herhalen dit over en voorbij. 

Dus nu kunnen we samenvoegen die twee helften. En dat is wat we hier doen. Dus de zwarte lijn net verdeelde de linkerhelft en de rechterhelft van deze soort onderdeel. 

We vergelijken de kleinste waarde aan de linkerkant van de array-- of neem me niet kwalijk, de kleinste waarde van de linkerhelft de kleinste waarde van het recht de helft en vind dat drie kleiner is. En nu een beetje een optimalisatie, toch? Er is eigenlijk niets links op de linkerkant. 

Er is niets overgebleven aan de linkerkant, dus we kunnen efficiënt gewoon move-- kunnen we verklaren de rest van het is eigenlijk gesorteerd en gewoon vastzetten op, want er is niets anders om mee te vergelijken. En we weten dat de rechterzijde de rechterzijde is gesorteerd. 

OK, dus laten we nu weer bevriezen en erachter te komen waar we zijn in het verhaal. In de totale matrix, wat hebben we bereikt? We hebben eigenlijk te bereiken nu de stappen één en stap twee. We naargelang de linker helft, en we naargelang de rechter helft. 

Dus nu, alles wat overblijft is voor ons die twee helften samen te voegen. Dus we vergelijken met de laagste waarde element van elke helft van de array beurt en gaan. Een daarvan is minder dan drie, dus men gaat. 

Twee minder dan drie, dus twee gaat. Drie minder dan 5, dus drie gaat. Vier minder dan 5, dus vier gaat. Dan is vijf minder dan zes, en zes is dat alles blijft. 

Nu, ik weet het, dat was veel trappen. En we hebben veel links geheugen in ons kielzog. En dat is wat die grijze vierkantjes zijn. En het waarschijnlijk voelde als die nam een veel langer dan insertion sort, bel sort of selectie sorteren. 

Maar in feite, omdat Veel van deze processen gebeuren op hetzelfde tijd-- dat is iets wat we zullen, nogmaals, praten over als we praten over recursie in een toekomstige video-- Dit algoritme eigenlijk duidelijk is fundamenteel anders dan iets we eerder hebben gezien maar ook significant Meer efficiënt. 

Waarom is dat? Nou, in het ergste geval, we n elementen splitsen en vervolgens recombineren hen. Maar toen we recombineren ze, wat we doen is in feite een verdubbeling van de grootte van de kleinere matrices. We hebben een heleboel één element arrays die we effectief combineren in twee elementen arrays. En dan nemen we die twee element arrays en deze combineren in vier element arrays, enzovoort, enzovoorts, enzovoorts, totdat we een enkele n element array. 

Maar hoeveel verdubbelingen duurt het om n te krijgen? Denk terug aan het telefoonboek voorbeeld. Hoe vaak hebben we te scheuren het telefoonboek in de helft, hoeveel meer tijden moeten we het telefoonboek scheuren in de helft, als de grootte van het telefoonboek verdubbelde? Er is slechts één, toch? 

Dus er is een soort van logaritmische element hier. Maar ook nog minstens kijken naar alle van de n elementen. Dus in het ergste geval, samenvoegen soort loopt in n log n. We moeten kijken naar alle n elementen, en we hebben om ze te combineren samen in log n sets van stappen. In het beste geval, de array is perfect opgelost. Dat is geweldig. Maar gebaseerd op het algoritme wij hier we hebben nog steeds te splitsen en recombineren. Hoewel in dit geval recombineren is een soort van ineffectief. Het is niet noodzakelijk. Maar we nog steeds gaan door het hele proces toch. 

Dus in het beste geval en in het ergste geval, dit algoritme draait in n log n tijd. Samenvoegen soort is zeker een beetje lastiger dan de andere grote sortering algoritmen we hebben gesproken over CS50, maar is aanzienlijk krachtiger. 

En dus als je ooit vinden gelegenheid om het nodig hebben of te gebruiken om te sorteren grote dataset, krijgen je hoofd rond het idee van recursie gaat echt krachtig te zijn. En het gaat om uw programma's echt veel efficiënter gebruik samenvoegen soort versus iets anders. Ik ben Doug Lloyd. Dit is CS50.