[Мусиц плаиинг] 

Даг Ллоид: У реду, тако да стапања сорта је још један алгоритам да можемо користити да средимо елементи низа. Али, као што ћемо видети, то има веома фундаментална разлика од селекције методу, буббле врста, и уметање врста да буде заиста лепо паметно. 

Основна идеја спајања сорта је за сортирање низова мање а затим комбинују те низова заједно, или спајање томе-- отуд и име-- у сортиране. Начин на који спајају врста ради ово је за усклађивање алата зове рецурсион, што је оно што ћемо да говоримо о ускоро, али нисмо баш разговарали о још. 

Овде је основна идеја стапања врсте. Сортирај левој половини низа, под претпоставком н је већи од 1. А шта ја мислим кад кажем под претпоставком н је већа од 1 је, Мислим да се можемо сложити да ако низ састоји само од једног елемента, то је средјено. Ми заправо не треба да ништа на њу. Можемо само да прогласи да се сортирају. То је само један елемент. 

Дакле, Псеудокод, опет, сортирање левој половини низа, онда сортирање право пола низ, затим спајање две половине заједно. Сада, већ можда бити мислећи, некако само Изгледа да кријеш од до-- нисте заправо ради ништа. Кажеш да сортирате лево половина, сортирање десној половини, али не говориш ми како то радиш. 

Али запамтите да докле год низ је један елеменат, можемо прогласити поредани. Онда можемо да их објединити. И то је заправо Основна идеја иза стапања врсте, је да га разбити, тако да Ваши низови су величине једног. И онда обнову одатле. 

Мерге сорта је дефинитивно компликован алгоритам. И то је такође мало компликовано за визуелизацију. Дакле, надамо се, визуализација да имам овде ће вам помоћи да пратите. И ја ћу дати све од себе да исприча ствари и наставите кроз ово мало више споро од других само да надамо се спусти главу око идеје иза стапања врсте. 

Дакле, имамо исти низ као други сортирање алгоритам Видеос ако сте видели томе-- шест елеменат низ. И наш Псеудокод код овде је некако лева половина, сортирање десној половини, спојити две половине заједно. Дакле, хајде да искористим ову веома тамно цигла црвена низ и сортирање левој половини тога. 

Дакле, за сада, идемо да игнорише ствари на десној страни. То је тамо, али смо није на још том кораку. Нисмо у разврстати десна половина низа. Ми смо на врсти левој страни половини низа. И само због да буде мало више јасно, тако да се може односити шта корак смо на ти, Идем да упалимо боја овог сета до наранџасте. Сада, ми смо и даље говоримо о саме Лева половина оригиналног низа. Али надам се да ће бити у стању да односе се боје разних предмета, то ће учинити мало више јасно шта се овде дешава. 

У реду, тако да сада имамо три елемента низа. Како да сортирамо левој половини ове Арраи, која је и даље овај корак? Покушавамо да учини нешто леви половина цигла црвена арраи-- од којих је левог дела Сада сам обојен наранџасто. 

Па, можемо покушати и поновите овај процес поново. Дакле, ми смо још увек у средини покушава да средим лева половина пуног спектра. Лева половина Арраи, ја ћу да произвољно одлучите да је лева половина ће бити мањи од десне половине, јер се ово догоди се састоје из три елемента. 

И тако ћу да кажем да је лева половина леве половине арраи је само елемент пет. Пет, бити један елемент Арраи, знамо како то да средим. И тако пет сортира. Ми ћемо да се изјасне да. То је један елемент низ. 

Дакле, сада смо поредани лева половина леве халф-- односно, ми смо поредани лева половина поморанџе. Дакле, сада, како би се и даље потпуна лева половина укупни арраи је, морамо да учини нешто десну половину од поморанџе, или ове ствари. Како ми то радимо? Па, имамо низ два елемента. Тако да можете сортирати левој половини низа, који је два. Два је један елеменат. Дакле, то је поредани по дефаулту. Онда можете сортирати десне половине те дио низа, оног. То је нека врста по дефаулту. 

Ово је сада први пут ми смо дошли до стапања корак. Завршили смо, иако ми смо сада некако угнијежђени довн-- и то је нека врста зезнуто ствар са рекурзије је, морате да држиш присебност где смо. Тако некако смо си левице пола порције наранџасте. 

И сада, ми смо у сред сортирање право пола порције поморанџе. И у том процесу, ми смо сада о да буде на кораку, спојити две половине заједно. Када погледамо два дела од низа, видимо два и један. Који елеменат је мањи? Један. 

Тада који елеменат је мањи? Па, то је два или ништа. Тако да је два. Дакле, сада, само да поново оквир где смо у контексту, смо поредани лева половина поморанџе и десна половина порекла. Знам да сам промијенио боје опет, али то је где смо били. А разлог зашто сам ово урадио је зато што процес да настави, итератинг доле. Ми смо поредани лево половина бивше поморанџе и десна половина бивше поморанџе. 

Сада, морамо да споји оне две половине заједно тоо. То је корак смо. Тако да смо размотрити све елементи који су сада зелена, лева половина некадашњег низа. И ми спојити оне коришћењем истог поступка јесмо за спајање два а пре месец само тренутак. 

Лева половина, најмањи елемент на левој половини је пет. Најмањи елемент на десна половина је један. Која од њих је мање? Један. 

Најмањи елемент на лева половина је пет. Најмањи елемент на десна половина је два. Шта је најмањи? Два. И онда на крају пет и ништа, можемо рећи пет. 

У реду, тако да велика слика, хајдемо предах за секунду и схватити где смо. Ако смо кренули од самом почетку, ми сада завршена за укупни низ само овде један корак од Псеудокод кода. Ми смо поредани лева половина низа. 

Подсетимо се да оригинални Наређење је било пет, два, један. До пролази кроз овај процес и гнезде се и понавља, наставља да се пробије тај проблем у мање и мање делове, сада смо завршили корак један од псеудокоду за цео почетне низа. Ми смо поредани своју левој половини. 

Дакле, сада да не смрзне. А сада да сортирају право половина некадашњег низа. И ми ћемо то урадити до пролази кроз исти итеративни Процес разбијање ствари доле а затим их спајањем. 

Тако је лева половина црвене или лево пола десног половине оригинала Арраи, ја ћу да кажем три. Опет, ја сам био доследан овде. Ако имате непаран број елемената га, није битно да ли је да на лево једна мања или право један мањи. 

Оно што је битно је да кад год вас наилазе овај проблем у спровођењу Стапање, морате бити доследни. Или увек треба да направи лева страна мања или увек треба да десна страна мања. Ево, ја сам изабрао да увек чине лева страна мања када је мој низ, или моје под-арраи је од непарног величине. 

Три је један елеменат, па је средјено. Ми смо искористио ту претпоставку током целог нашег процеса до сада. Па сада нека је врста право половина десне половине, или десна половина црвено. 

Опет, морамо да поделимо ово. Ово није један елемент низ. Ми не можемо да прогласи поредани. И тако прво, идемо за сортирање левој половини. 

Лева половина је један елеменат, тако да је на неки начин по дефаулту. Онда ћемо да учини нешто право половине, што је једна елемент. То је поредани по дефаулту. А сада, можемо спојити та два заједно. Четири је мања, и онда шест је мањи. 

Опет, шта смо урадили у овом тренутку? Ми смо поредани лево половина десне половине. Или да се вратимо у оригиналу боје које су биле тамо, ми смо поредани лево половина је мекша ред. Првобитно је било мрачно цигла црвене и сада је мекша црвена, или је то била мекша црвено. 

А онда смо поредани десна половина је мекша ред. Сада, добро, они су зелени опет, само јер ћемо кроз процес. И морамо да поновим и због овога више. 

Дакле, сада можемо спојити оне две половине заједно. И то је оно што радимо овде. Тако црне линије само подељена левој половини и десна половина ове врсте дела. 

Ми упоредите најмању вриједност на левој страни арраи-- или извините, најмањи Вредност леве половине до најситнијих вриједности права пола и да пронађу три мања. А сада мало оптимизацију, зар не? Заправо постоји ништа оставио на левој страни. 

Нема ништа преостало на левој страни, тако да можемо ефикасно Само мове-- можемо прогласити остатак је у ствари поредани и само тацк даље, јер не постоји ништа друго да упоредите против. А знамо да је десна страна са десне стране је средјено. 

У реду, тако да сада идемо опет смрзне и схватити где смо у причи. У укупној низа, шта смо постигли? Стварно смо постигли Сада кораке један и два корака. Ми поредани левој половини, и смо поредани десној половини. 

Тако сада, све што остаје за нас да споји ове две половине заједно. Дакле, поредимо најнижа вреднована елеменат сваког половини низа заузврат и наставите. Један од њих је мање од три, тако иде. 

Два је мање од три, па две иде. Три је мања од 5, па три иде. Четири мања од 5, па су четири иде. Тада је пет мање од шест, а шест је све што је остало. 

Сада, знам да је доста корака. И ми смо оставили много меморије у нашој после. И то је оно што ти сива тргови су. И то је вероватно осећао као да трајало је много дуже него унесени врсте, мехур врста, или избор врста. 

Али, у ствари, јер Многи од тих процеса се догађа у исто времена-- готово што је нешто ћемо, опет, разговарали када говоримо о рецурсион у будућности видео-- овај алгоритам у ствари Јасно је фундаментално другачији од свега видели смо раније али је такође значајно ефикаснији. 

Зашто је то? Па, у најгорем сценарио, имамо подијелити н елемената до а затим их рекомбинује. Али када смо рекомбинује их, шта радимо је у основи удвостручује величина мањих низова. Имамо гомилу једног елемента низови да ефикасно комбинују у две низовима елемената. А онда узмемо оне два низа елемената и комбиновати их заједно у Четири елемента низови, и тако даље, и тако даље, и тако даље, све док не имају један Н елемент низа. 

Али колико дуплирања је потребно да стигнете до н? Сетите се телефонски именик пример. Колико пута морамо да растуре телефонски именик на пола, колико још пута морамо да поцепа телефонски именик на пола, ако је величина именика удвостручио? Постоји само један, зар не? 

Дакле, постоји нека врста логаритамске елеменат овде. Али ми такође тек треба да најмање погледај све н елемената. Дакле, у најгорем случају, спајање врста ради у Н лог н. Морамо да погледамо све н елемената, и ми морамо да их комбинујете заједно у дневнику н сета корака. У најбољем случају, низ се савршено поредани. Одлично. Али, на основу алгоритма имамо овде, ипак морамо да поделимо и рекомбинује. Иако у овом случају, комбинујући је некако неефикасна. То није потребно. Али ми и даље пролазе кроз цео процес свеједно. 

Дакле, у најбољем случају ау најгорем случају, Овај алгоритам ради у дневнику н н време. Мерге сорта је дефинитивно мало компликованије од других алгоритама главних разврставања причали смо о ЦС50, али је знатно моћнији. 

И тако, ако икада наћи прилика да је потребно или да га користите за Поређати велики скуп података, добијање главу око идеје рекурзије ће бити веома моћна. И да ће направити своје програми заиста много ефикаснији користите стапања врста у односу на било шта друго. Ја сам Доуг Лојд. Ово је ЦС50.