[MUSIC nagpe-play] 

DOUG LLOYD: OK, sa gayon ang isang merge uri ay isa pang algorithm na maaari naming gamitin upang uriin ang ang mga elemento ng isang array. Ngunit bilang namin makita, ito ay nakuha ng isang napaka pangunahing pagkakaiba mula sa pagpili ng uri, bubble uri, at uri pagpapasok na gawin itong tunay na medyo matalino. 

Ang pangunahing ideya sa likod merge uri ay upang ayusin mas maliit na array at pagkatapos ay pagsamahin ang mga array sama-sama, o pagsamahin them-- samakatuwid ang name-- sa inayos order. Ang paraan na pagsamahin ang mga uri ito ay sa pamamagitan ng pagdaragdag ng isang kasangkapan tinatawag na recursion, na kung saan ay kung ano ang kami ay pagpunta sa pakikipag-usap tungkol sa lalong madaling panahon, ngunit kami ay hindi talagang uusapang tungkol sa pa. 

Narito ang mga pangunahing ideya sa likod pagsasama-uuri. Pagsunud-sunurin ang kaliwang kalahati ng array, sa pag-aakala n ay mas malaki sa 1. At kung ano ang ibig sabihin ko kapag sinasabi ko sa pag-aakala n ay mas malaki sa 1 ay, Sa tingin ko maaari naming sumang-ayon na kung ang isang array ay binubuo lamang ng isang solong elemento, ito ay pinagsunod-sunod. Hindi namin talagang kailangan gumawa ng kahit ano sa mga ito. Maaari naming ipahayag lamang ito upang maging inayos. Ito ay lamang ng isang solong elemento. 

Kaya ang pseudocode, muli, ay ayusin ang kaliwa kalahati ng array, pagkatapos ay ayusin ang kanang kalahati ng array, pagkatapos ay pagsamahin ang dalawang bahagi ng magkasama. Ngayon, mayroon na maaari kang maging pag-iisip, ito uri ng lamang tunog tulad ng ikaw ay paglagay off the-- hindi ka talaga ginagawa kahit ano. Ikaw ay nagsasabi uriin ang kaliwang kalahati, uri-uriin ang kanang kalahati, ngunit hindi ka nagsasabi akin kung paano mo ito ginagawa. 

Ngunit tandaan na hangga't isang array ay isang solong elemento, maaari naming ipahayag ito pinagsunod-sunod. Pagkatapos ay maaari naming lamang pagsamahin ang mga ito nang magkakasama. At na aktwal na ang pangunahing ideya sa likod ng pagsasama-uuri, ay upang basagin ito pababa upang iyong array ay ang laki ng isa. At pagkatapos mong gawing muli mula doon. 

Pagsamahin ang mga uri ay tiyak isang komplikadong algorithm. At ito ay isang maliit na ring kumplikado upang maisalarawan. Kaya sana, ang visualization na ako Mayroon dito ay makakatulong kang sumunod. At kukunin ko na subukan ang aking pinakamahusay sa magsaysay bagay at magpatuloy sa pamamagitan ng isang maliit na mas mabagal kaysa sa iba pang mga iyan lamang na sana ay makakuha ng iyong ulo sa paligid ng mga ideya sa likod ng pagsasama-uuri. 

Kaya kami ay may parehong array bilang ang iba pang mga pag-uuri algorithm video kung ang iyong nakita them-- isang array anim na elemento. At ang aming pseudocode code dito ay uri sa kaliwang kalahati, uri-uriin ang kanang kalahati, pagsamahin ang dalawang halves magkasama. Kaya sabihin ito napaka dark red brick array at ayusin ang kaliwa kalahati nito. 

Kaya para sa oras, kami ay pagpunta upang huwag pansinin ang mga bagay-bagay sa kanan. Ito ay doon, ngunit hindi namin hindi sa na pa-hakbang. Ikinalulungkot namin na hindi sa uri-uriin ang mga kanang kalahati ng array. Kami ay sa mga uri sa kaliwa kalahati ng array. At para lamang sa kapakanan ng pagiging isang maliit na mas malinaw, kaya ang maaari kong sumangguni sa kung ano ang hakbang na hindi namin sa, Pupunta ako upang lumipat sa kulay ng hanay na ito sa orange. Ngayon, pinag-uusapan pa rin kami tungkol sa parehong kaliwa kalahati ng orihinal na array. Ngunit ako umaasa na sa pamamagitan ng kawalan ng kakayahang sumangguni sa mga kulay ng iba't-ibang mga bagay, ito ay gumawa ito ng kaunti pa malinaw kung ano ang nangyayari sa dito. 

OK, kaya ngayon kami ay may isang tatlong element ng array. Paano namin-uri-uriin ang kaliwang kalahati ng array, na kung saan ay pa rin ang hakbang na ito? Kami ay sinusubukan upang ayusin ang kaliwang kalahati ng mga brick red array-- sa kaliwang kalahati ng kung saan Ngayon ko na kulay na ako orange. 

Well, maaari naming subukan at ulitin muli ang proseso na ito. Kaya ikaw pa rin namin sa gitna ng sinusubukan na ayusin sa kaliwang kalahati ng buong array. Ang kaliwang kalahati ng array, ako lamang ang pagpunta nagkataon magpasya na ang kaliwang kalahati ay mas maliit kaysa sa kanang kalahati, dahil ito ang mangyayari sa mga binubuo ng tatlong elemento. 

At kaya ako pagpunta sa sabihin na ang kaliwang kalahati ng kaliwang kalahati ng array ay lamang ang mga elemento ng limang. Five, pagiging isang solong elemento array, alam namin kung paano ayusin ito. At kaya limang ay pinagsunod-sunod. Kami ay pagpunta na idedeklara na. Ito ay isang solong array elemento. 

Kaya ngayon inayos na namin ang mga kaliwang kalahati ng kaliwang half-- o sa halip, na inayos namin ang kaliwang kalahati ng orange. Kaya ngayon, upang pa rin kumpleto kaliwang kalahati ang kabuuang array, ang kailangan namin upang ayusin ang mga karapatan sa kalahati ng orange, o mga bagay-bagay na ito. Paano namin gawin iyon? Well, kami ay may isang array ng dalawang elemento. Kaya maaari naming ayusin ang kaliwa kalahati ng array, na kung saan ay dalawang. Dalawang ay isang solong elemento. Kaya ito ay nakaayos ayon sa default. Pagkatapos ay maaari naming ayusin ang mga karapatan sa kalahati ng bahaging iyon ng array, ang isa. Iyan ay ang uri ng default. 

Ito ay ngayon sa unang pagkakataon naabot na namin ang isang hakbang merge. Kami ay nakumpleto na, bagaman na namin ngayon uri ng nested down-- at na ang mga uri ng mga mapanlinlang bagay na may recursion ay, kailangan mong ilagay ang iyong ulo tungkol sa kung saan tayo ay. Kaya hindi namin uri ng kaliwang kalahati ng mga orange na bahagi. 

At ngayon, hindi namin sa gitna ng pag-uuri ang kanang kalahati ng orange bahagi. At sa prosesong iyon, kami ay tungkol sa ngayon na sa hakbang na ito, pagsamahin ang dalawang halves magkasama. Kapag tinitingnan namin ang dalawang bahagi ng array, nakita namin ng dalawa at isa. Aling elemento ay mas maliit? One. 

Pagkatapos na elemento ay mas maliit? Well, ito ay ang dalawa o wala. Kaya ito ay dalawa. Kaya ngayon, sa muli-frame lamang kung saan tayo ay sa konteksto, may inayos namin ang mga kaliwang kalahati ng orange at ang kanang kalahati ng pinanggalingan. Alam ko ako ay nagbago ang mga kulay muli, ngunit iyan ay kung saan namin. At ang dahilan ginawa ko ito ay dahil ang proseso na ito ay pagpunta sa panatilihin ang pagpunta, iterating down. Inayos na namin ang kaliwang kalahati ng mga dating orange at ang kanang kalahati ng dating orange. 

Ngayon, kailangan namin upang sumanib sa mga dalawang kalahati magkasama masyadong. Iyan ang step kami sa. Kaya isaalang-alang namin ang lahat ng elemento na green ngayon, sa kaliwang kalahati ng orihinal na array. At sumanib namin ang mga gamit ang parehong proseso ginawa namin para sa pinagsasama ang dalawang at isa lamang ng isang sandali ang nakalipas. 

Ang kaliwang kalahati, ang pinakamaliit elemento sa kaliwang kalahati ay limang. Ang pinakamaliit na elemento sa ang kanang kalahati ay isa. Alin sa mga ito ay mas maliit? One. 

Ang pinakamaliit na elemento sa sa kaliwang kalahati ay limang. Ang pinakamaliit na elemento sa ang kanang kalahati ay dalawa. Ano ang pinakamaliit? Dalawang. At pagkatapos ay sa wakas limang at wala, maaari naming sabihin lima. 

OK, kaya malaki larawan, sabihin kumuha ng pahinga para sa isang segundo at malaman kung saan kami. Kung nagsimula kami mula sa Na sa simula, kami ay may ngayon nakumpleto para ang kabuuang array lamang isang hakbang ng pseudocode code dito. Kami ay inayos ang kaliwang kalahati ng array. 

Alalahanin na ang mga orihinal na sunod ay limang, dalawa, isa. Sa pamamagitan ng pagpunta sa pamamagitan ng proseso na ito at mamahinga pababa at paulit-ulit, patuloy na putulin ang problema down sa mas maliit at mas maliit na bahagi, ngayon kami ay nakumpleto hakbang isa sa pseudocode para sa buong panimulang array. Kami ay inayos kaliwang kalahati nito. 

Kaya ni-freeze doon ngayon hayaan. At ayusin sa ngayon hayaan kalahati ng orihinal na array. At kami ay pagpunta upang gawin iyon sa pamamagitan ng pagpunta sa pamamagitan ng parehong umuulit proseso ng paglabag bagay down at pagkatapos ay pinagsasama ang mga ito nang magkakasama. 

Kaya ang kaliwang kalahati ng pula, o sa kaliwang kalahati ng kanang kalahati ng orihinal array, ako ng pagpunta sa sabihin ay tatlo. Muli, ako pagiging pare-pareho dito. Kung ikaw ay may isang kakaiba bilang ng mga elemento, ito ay hindi talagang mahalaga kung mong gawin ang mga ditong isang mas maliit o ang karapatan ng isa na mas maliit. 

Ano ang mga bagay na kahit kailan mo magkasalubong ang problemang ito sa pagsasagawa isang merge, kailangan mo upang maging pare-pareho. Kang mag-laging kailangan upang gumawa ng isang kaliwang bahagi ng mas maliit na o laging kailangan upang gumawa ng mga sa kanang bahagi ng mas maliit. Dito, pinili ko na laging gawin ang kaliwang bahagi ng mas maliit na kapag ang aking mga array, o ang aking sub-array, ay ng isang kakaibang sukat. 

Tatlong ay isang solong elemento, at sa gayon ito ay pinagsunod-sunod. Leveraged namin na palagay buong aming buong proseso sa ngayon. Kaya ngayon ayusin ni kanan ipaalam kalahati ng kanang kalahati, o ang karapatan sa kalahati ng mga pula. 

Muli, kailangan nating nahati ito pababa. Ito ay hindi isang solong array elemento. Hindi namin ipahayag ito pinagsunod-sunod. At kaya una, kami ay pagpunta upang ayusin ang kaliwang kalahati. 

Ang kaliwang kalahati ay isang solong elemento, kaya ito ay uri ng sa pamamagitan ng default. Pagkatapos kami ay pagpunta sa uri-uriin ang mga karapatan kalahati, na kung saan ay isang solong elemento. Ito ay nakaayos ayon sa default. At ngayon, kami ay maaaring sumanib sa mga dalawang magkasama. Apat ay mas maliit, at pagkatapos ng anim na ito ay mas maliit. 

Muli, kung ano ang mayroon kami tapos sa puntong ito? Inayos na namin ang kaliwang kalahati ng mga karapatan sa kalahati. O balik sa orihinal na kulay nandoon, Inayos na namin ang kaliwang kalahati ng hinaan red. Ito ay orihinal na isang madilim na ladrilyo red at ngayon ito ay isang hinaan pula, o ito ay isang hinaan red. 

At pagkatapos Inayos na namin ang mga kanang kalahati ng hinaan red. Ngayon, well, ang mga ito ay berde muli, lamang dahil kami ay pagpunta sa pamamagitan ng isang proseso. At kami ay may upang ulitin ito nang paulit-ulit. 

Kaya ngayon maaari naming pagsamahin ang mga dalawang kalahati magkasama. At na kung ano ang ginagawa namin dito. Kaya ang itim na linya lamang nahahati sa kaliwang kalahati at ang kanang kalahati ng uri na ito bahagi. 

Inihambing namin ang pinakamaliit na halaga sa kaliwang bahagi ng array-- o patawarin ninyo ako, ang pinakamaliit halaga ng kaliwang kalahati sa pinakamaliit na halaga ng mga karapatan half at natagpuan na ang tatlong ay mas maliit. At ngayon ng isang piraso ng isang pag-optimize, i-right? Mayroon talagang walang iniwan sa kaliwang bahagi. 

May walang natitirang ay sa kaliwang bahagi, upang maaari naming mahusay move-- lamang maaari naming ipahayag ang natitirang bahagi ng mga ito ay tunay na inayos at tak lang ito on, dahil mayroong wala iba pa upang ihambing kumpara sa. At nalalaman natin na ang kanang bahagi ng kanang bahagi ay nakaayos. 

OK, kaya ngayon sabihin freeze muli at malaman kung saan tayo sa kuwento. Sa pangkalahatang array, kung ano kami ay tapos na? Talaga namin ang magawa ang ngayon hakbang isa at dalawang hakbang. Inayos namin ang kaliwang kalahati, at Inayos namin ang karapatan kalahati. 

Kaya ngayon, ang lahat na nananatiling ay para sa amin upang sumanib sa mga dalawang halves magkasama. Kaya namin ihambing ang pinakamababang minamahal sangkap ng bawat kalahati ng array naman at magpatuloy. Ang isa ay mas mababa sa tatlong, para magpunta. 

Dalawang ay mas mababa kaysa sa tatlong, kaya dalawang napupunta. Tatlong ay mas mababa sa 5, kaya tatlong napupunta. Apat ay mas mababa sa 5, kaya apat na napupunta. Pagkatapos ng limang ay mas mababa sa anim na, at anim ay ang lahat na nananatiling. 

Ngayon, alam ko, na noon ay isang pulutong ng mga hakbang. At kami iniwan na ng maraming ng memory sa aming wake. At na kung ano ang mga kulay-abo na kahon ay. At ito marahil ang nadama tulad na kinuha ng isang maraming mas mahaba kaysa uuri, bubble uri-uriin, o uri ng pagpili. 

Ngunit ang tunay na, dahil ang isang pulutong ng mga proseso ay nangyayari sa parehong time-- na kung saan ay isang bagay na ipapakita namin, muli, makipag-usap tungkol sa usaping recursion sa isang hinaharap video-- algorithm na ito ang tunay malinaw ay panimula naiiba kaysa sa anumang bagay nakita natin dati ngunit ding makabuluhang mas mahusay. 

Bakit na? Well, sa pinakamasama case na sitwasyon, kami ay sa split n elemento up at pagkatapos ay muling pagsamahin ang mga ito. Ngunit kapag muling pagsamahin namin ang mga ito, kung ano ang aming ginagawa ay talaga pagdodoble ang laki ng mas maliit na array. Kami ay may isang bungkos ng isang elemento array na namin epektibong pagsamahin sa dalawang array elemento. At pagkatapos ay dadalhin namin ang mga dalawang array elemento at pagsamahin ang mga ito nang magkakasama sa apat na array na sangkap, at iba pa, at iba pa, at iba pa, hanggang sa kami magkaroon ng isang solong array n element. 

Ngunit kung gaano karaming doublings aabutin upang makakuha n? Isipin bumalik sa halimbawa phone book. Gaano karaming beses ang mayroon kami sa mapunit ang telepono ng libro sa kalahati, kung paano mas maraming beses kailangan namin upang pilasin ang telepono ng libro sa kalahati, kung ang laki ng mga libro ng telepono Dinoble? May isa lang, di ba? 

Kaya may ilang mga uri ng logarithmic elemento dito. Ngunit pa rin namin ay mayroon din na hindi bababa sa tingnan ang lahat ng mga n elemento. Kaya sa pinakamasama kaso sitwasyon, sumanib-uuri ay tumatakbo sa n log n. Mayroon kaming upang tumingin sa lahat ng mga n elemento, at kami ay upang pagsamahin ang mga ito magkasama sa log n set ng mga hakbang. Sa ang pinakamahusay na kaso sitwasyon, array ay ganap na pinagsunod-sunod. Mabuti iyan. Ngunit batay sa mga algorithm na namin dito, mayroon pa rin kaming mag-split at muling pagsamahin. Kahit na sa kasong ito, ang recombining ay uri ng walang saysay. Ito ay hindi kinakailangan. Ngunit kami ay pumunta pa rin sa pamamagitan ang buong proseso pa rin. 

Kaya sa pinakamahusay na kaso at sa pinakamasama kaso, algorithm na ito ay tumatakbo sa n log n oras. Pagsamahin ang mga uri ay talagang nangangailangan ng kaunting kasanayan kaysa sa iba pang mga pangunahing pag-uuri algorithm Na-usapan natin ang tungkol sa CS50 ngunit ay malaki mas malakas na. 

At kaya kung sakaling mahanap mo okasyon sa kailangan ito o upang gamitin ito upang maipagsama-sama ang isang malaking hanay ng data, pagkuha ang inyong ulo sa paligid ng ideya ng recursion ay magiging talagang malakas. At ito ay pagpunta sa gawin ang iyong mga talagang mas mahusay na mga programa gamit sumanib uri laban sa anumang bagay. Ako Doug Lloyd. Ito ay CS50.