[Гуляе музыка] 

Даг Lloyd: ОК, так што зліццё роду з'яўляецца яшчэ адным алгарытмам што мы можам выкарыстоўваць, каб разабрацца элементы масіва. Але, як мы ўбачым, ён атрымаў вельмі прынцыповая розніца ад выбару гатунку, бурбалка сартаваць і сартаванне ўстаўкамі якія робяць яго сапраўды вельмі разумны. 

Асноўная ідэя зліцця сартавання для сартавання дробных масіваў а затым аб'яднаць гэтыя масівы разам, або аб'яднаць them-- такім чынам name-- ў адсартаваным парадку. Такім чынам, што сартаванне зліццём робіць гэта, выкарыстоўваючы інструмент называецца Рэкурсія, што і мы будзем казаць аб ў бліжэйшы час, але мы не казалі пра яшчэ. 

Вось асноўная ідэя сартавання зліццём. Сартаваць левую палову масіва, пры ўмове, N больш 1. І тое, што я маю на ўвазе, калі кажу, пры ўмове, N больш, чым 1, Я думаю, што мы можам пагадзіцца, што, калі масіў складаецца толькі з аднаго элемента, гэта сартуецца. Мы не на самай справе трэба каб зрабіць што-небудзь з ім. Мы можам проста аб'явіць яго быць адсартаваныя. Гэта ўсяго толькі адзін элемент. 

Так псевдокод, зноў жа, сартаваць левую палову масіва, затым адсартаваць правая палова масіў, а затым аб'яднаць дзве палоўкі разам. Цяпер, ужо вы маглі б быць думаючы, што гэта накшталт толькі Падобна на тое, вы адкладалі the-- Вы на самой справе не робяць нічога. Вы кажаце адсартаваць левую палова, сартаваць правую палову, але ты не кажаш мне, як ты гэта робіш. 

Але памятайце, што пакуль масіў з'яўляецца адзіным элементам, мы можам аб'явіць яго сартаваць. Тады мы можам проста абяднаць іх разам. І гэта на самай справе Асноўная ідэя ззаду сартавання зліццём, гэта разбіць яго такім чынам, што Вашы масівы маюць памер аднаго. І тады вы аднавіць адтуль. 

Зліццё роду, безумоўна, складаны алгарытм. І гэта таксама трохі складаней візуалізаваць. Так, мы спадзяемся, візуалізацыя, што я ёсць тут, дапаможа Вам прытрымлівацца ўздоўж. І я буду старацца з усіх сіл, каб распавесці рэчы і прайсці праз гэта крыху больш, павольней, чым астатніх проста мы спадзяемся атрымаць вашу галаву вакол ідэй, якія ляжаць сартавання зліццём. 

Такім чынам, мы маем той жа масіў у якасці іншыя алгарытм сартавання відэа калі вы бачылі them-- Масіў шэсць элемент. І наша псевдокод тут код з'яўляецца свайго роду левая палова, сартаваць правую палову, аб'яднаць дзве палоўкі разам. Такім чынам, давайце гэта вельмі цёмна чырвоны цэгла масіва і адсартаваць левую палову. 

Так на дадзены момант, мы збіраемся ігнараваць рэчы справа. Гэта там, але мы ня на гэтым кроку яшчэ. Мы не Сартаванне Правая палова масіва. Мы ў той левага палова масіва. І толькі дзеля быць трохі больш ясна, так што я магу звярнуцца на тое, што крок мы на, Я збіраюся пераключыць Колер гэтага набору апельсіна. Зараз, мы ўсё яшчэ гаворым пра ж левая палова зыходнага масіва. Але я спадзяюся, што, будучы ў стане см колеру розных прадметаў, гэта зробіць яго крыху больш ясна, што тут адбываецца. 

ОК, так што цяпер у нас ёсць тры элемента масіва. Як мы сартуем левую палову гэтага Масіў, які да гэтага часу гэты крок? Мы спрабуем, каб адсартаваць левую палова з чырвонай цэглы array-- левая палова якога Я цяпер афарбаваны ў аранжавы колер. 

Ну, мы маглі б паспрабаваць паўтарыць гэты працэс зноў. Такім чынам, мы ўсё яшчэ ў Сярэдзіна спрабуючы разабрацца левая палова поўнай масіва. Левая палова Масіў, я толькі збіраюся адвольна вырашаць, што левая палова будзе менш, чым у правай палове, таму што гэта адбываецца з складаецца з трох элементаў. 

І таму я хачу сказаць, што левая палова левай палове масіва гэта проста элемент пяць. Пяць, ён быў адзін элемент Масіў, мы ведаем, як разбірацца. І так пяць сартуецца. Мы проста заявіць, што. Гэта адзін элемент масіва. 

Такім чынам, мы ў цяперашні час сартуюцца левая палова левай half-- дакладней, мы адсартаваныя левая палова памяранца. Так што цяпер, для таго, каб па-ранейшаму поўная левая палова агульнага масіва, мы павінны разабрацца ў правую палову апельсіна, або гэты матэрыял. Як мы гэта робім? Ну, у нас ёсць масіў з двух элементаў. Такім чынам, мы можам адсартаваць левую палову масіва, які два. Два гэта адзіны элемент. Так што гэта сартуецца па змаўчанні. Тады мы можам адсартаваць правую палову той частцы масіва, адзін. Гэта свайго роду па змаўчанні. 

Зараз гэта ў першы раз мы дасягнулі крок зліцця. Мы завяршылі, хоць мы зараз выгляд ўкладзеных down-- і гэта свайго роду хітры што з рэкурсіі, Вы павінны трымаць галаву пра тое, дзе мы знаходзімся. Такім чынам, мы свайго роду злева палова аранжавага часткі. 

І зараз, мы знаходзімся ў сярэдзіне сартавання правая палова аранжавага часткі. І ў гэтым працэсе, мы цяпер збіраецца быць на крок, аб'яднаць дзве палоўкі разам. Калі мы глядзім на дзве паловы масіва, мы бачым два і адзін. Які элемент менш? Адзін. 

Тады, які элемент менш? Ну, гэта два ці нічога. Так што гэта два. Так што цяпер, проста зноў кадр дзе мы знаходзімся ў кантэксце мы сартуюцца левая палова апельсіна а правая палова паходжання. Я ведаю, што я змяніў колеру зноў, але гэта, дзе мы былі. І прычына Я зрабіў гэта у тым, што гэты працэс працягваць ісці, паўтараючы ўніз. Мы адсартаваныя левы палова былога аранжавага а правая палова ранейшага аранжавага колеру. 

Цяпер нам трэба аб'яднаць тых, дзве палоўкі разам таксама. Гэта крок, які мы зараз знаходзіцеся. Такім чынам, мы разгледзім усе з элементы, якія ў цяперашні час з'яўляюцца зялёны, левая палова зыходнага масіва. І мы аб'яднаем тых, выкарыстоўваючы той жа самы працэс мы зрабілі для аб'яднання дзвюх і адзін толькі момант таму. 

Левая палова, найменшы элемент на левай палове пяць. Найменшую элемент на правая палова з'яўляецца адным. Які з іх з'яўляецца менш? Адзін. 

Найменшую элемент на левая палова пяць. Найменшую элемент на правая палова гэта два. Што найменшую? Два. І тады, нарэшце, пяць нічога, мы можам сказаць, пяць. 

Такім чынам, карціна, давайце перапынак на секунду і высветліць, дзе мы знаходзімся. Калі б мы пачалі з у самым пачатку, мы Цяпер завершаны агульная масіў толькі адзін крок кода псевдокода тут. Мы сартуюцца левая палова масіва. 

Нагадаем, што арыгінальны Загад быў пяць, два, адзін. Ідучы праз гэты працэс і гнездавання ўніз і паўтараць, працягваючы парушаць праблему на больш дробныя і больш дробныя часткі, мы ўжо завяршылі крок адзін з псевдокода на працягу ўсяго пачатковай масіва. Мы разабраліся левую палову. 

Так што цяпер давайце замарозіць там. А цяпер давайце разбярэмся права палова зыходнага масіва. І мы збіраемся зрабіць гэта, перажывае тое ж самае итеративный працэс разбурэння рэчы ўніз , А затым аб'ядноўваць іх разам. 

Такім чынам, левая палова з чырвоны ці левая палова правай паловы першапачатковага Масіў, я збіраюся сказаць, тры. Зноў жа, я тут быць паслядоўным. Калі ў вас ёсць няцотная Колькасць элементаў, яго на самай справе не мае значэння, Вы робіце левая менш або права паменш. 

Важна тое, што кожны раз, калі вам сутыкнуліся з гэтай праблемай у правядзенні зліццё, вам трэба быць паслядоўным. Вы альбо павінны заўсёды зрабіць левы бок менш ці заўсёды трэба зрабіць правая бок менш. Тут я выбраў, каб заўсёды зрабіць левы бок менш калі мой масіў, ці мой суб-масіва, з'яўляецца няцотным памеру. 

Тры ёсць адзін элемент, і таму ён адсартаваны. Мы выкарыстала гэта здагадка на працягу ўсёй нашай працэсе да гэтага часу. Так што цяпер давайце разбярэмся права палова правай палове, ці правая палова чырвонага. 

Зноў жа, мы павінны падзяліць гэта ўніз. Гэта не адзіны элемент масіва. Мы не можам аб'явіць яго сартаваць. І так па-першае, мы збіраемся сартаваць левую палову. 

Левая палова адзін элемент, так што гэта свайго роду па змаўчанні. Тады мы ідзем, каб адсартаваць права палова, што адзін элемент. Гэта сартуюцца па змаўчанні. І зараз, мы можам аб'яднаць гэтыя два разам. Чатыры менш, і затым шэсць менш. 

Зноў жа, тое, што мы зрабілі ў гэты момант? Мы адсартаваныя левы палова правай палове. Або вярнуцца да арыгіналу колеру, якія былі там, мы адсартаваныя левы палова мяккага чырвонага. Першапачаткова ён быў цёмна-цэгла чырвоны і цяпер гэта мякчэй чырвоны, ці гэта была мякчэй чырвоны. 

А потым мы сартуюцца Правая палова мяккага чырвонага. Цяпер, добра, яны зялёныя зноў, толькі таму што мы збіраемся праз працэс. І мы павінны паўтарыць гэта зноў і зноў. 

Так што цяпер мы можам аб'яднаць тых, дзве палоўкі разам. І гэта тое, што мы робім тут. Так чорнай лініі толькі падзяліць левую палову а правая палова гэтага роду часткі. 

Мы параўноўваем найменшае значэнне на левай баку array-- або, прабачце, найменшая Значэнне левай палове найменшаму значэнні правы палова і выявілі, што тры менш. А цяпер крыху аптымізацыі, праўда? Там насамрэч нічога пакінулі на левай баку. 

Там няма нічога астатнія на левай баку, таму мы можам эфектыўна проста move-- мы можам аб'явіць астатняе на самай справе сартуюцца і толькі лавіраваць яго на, таму што няма нічога яшчэ для параўнання. І мы ведаем, што правы бок з правага боку сартуецца. 

ОК, так што цяпер давайце зноў і замарозіць высветліць, дзе мы знаходзімся ў гісторыі. У агульным масіве, Што мы зрабілі? Мы на самай справе выканаць Цяпер крокі адно і другі этап. Мы адсартаваныя левую палову, і мы адсартаваныя правую палову. 

Так што цяпер, усё, што застаецца для нас аб'яднаць гэтыя дзве палоўкі разам. Такім чынам, мы параўноўваем самы нізкі цэніцца элемент кожнай палове масіва у сваю чаргу, і працягнуць. Адным з іх з'яўляецца менш чым тры, так што ідзе. 

Два менш трох, так што два ідзе. Тры менш чым 5, так тры ідзе. Чатыры менш, чым 5, так чацвёрка заходзіць. Тады пяць менш, чым шэсць, і шэсць гэта ўсё, што застаецца. 

Зараз, я ведаю, што было шмат крокаў. І мы пакінулі шмат памяці ў нашай хвалі. І гэта тое, што гэтыя шэрыя квадраты. І гэта, верагодна, адчуваў, што гэта ўзяў значна даўжэй, чым ўстаўкі роду, бурбалка сартаваць, ці выбар роду. 

Але на самой справе, таму што Многія з гэтых працэсаў адбываюцца ў той жа time-- што тое, што мы будзем, зноў жа, казаць, калі мы гаворым пра Рэкурсія ў будучыні video-- гэты алгарытм на самай справе ясна прынцыпова адрозніваецца ад усяго, мы бачылі раней але таксама значна больш эфектыўным. 

Чаму так? Ну, у горшым сцэнар, у нас ёсць падзяліць п элементаў да а затым зліваюць. Але калі мы аб'яднаць ім, што мы робім у асноўным падваенне Памер меншых масіваў. У нас ёсць куча аднаго элемента масівы, якія мы эфектыўна аб'яднаць у двух масівах элементаў. А потым мы возьмем тых, два масіва элемент і аб'яднаць іх разам у чатыры масіва элементаў, і гэтак далей, ня і гэтак далей, і гэтак далей, да таго часу, ёсць адзін масіў п элементаў. 

Але колькі падваення гэта, каб дабрацца да п? Ўспомніце, напрыклад тэлефоннай кнігі. Колькі разоў мы павінны ірваць тэлефонная кніга на палову, колькі яшчэ раз мы павінны ірваць тэлефонную кнігу напалову, калі памер тэлефоннай кнігі у два разы? Там толькі адзін, праўда? 

Так што нейкая лагарыфмічная элементам тут. Але мы таксама ўсё яшчэ ёсць, па меншай меры глядзець на ўсе п элементаў. Такім чынам, у горшым выпадку, сартаванне зліццём працуе ў п часопіса п. Мы павінны глядзець на усе п элементаў, і мы павінны аб'яднаць іх разам у часопісе н набораў крокаў. У лепшым выпадку, масіў выдатна адсартаваныя. Гэта выдатна. Але на аснове алгарытму мы маем тут, мы ўсё яшчэ павінны падзяліць, а затым. Хоць у гэтым выпадку рекомбинирующий накшталт неэфектыўнымі. Яна не патрэбна. Але мы па-ранейшаму ісці праз увесь працэс у любым выпадку. 

Такім чынам, у лепшым выпадку а ў горшым выпадку, гэты алгарытм працуе ў часопісе н н часу. Зліццё роду, безумоўна, крыху больш складана чым іншых асноўных алгарытмаў сартавання мы гаварылі пра CS50, але істотна больш магутным. 

І таму, калі вы калі-небудзь знайсці Нагодай для гэта трэба або выкарыстоўваць яго для сартавання вялікі набор дадзеных, атрыманне Ваша галава вакол ідэі рэкурсіі будзе вельмі магутны. І гэта будзе зрабіць свой праграмы сапраўды нашмат больш эфектыўна з дапамогай сартаванне зліццём супраць што-небудзь яшчэ. Я Дуг Лойд. Гэта CS50.