[Bermain muzik] 

DOUG LLOYD: OK, jadi merge yang jenis lagi algoritma lain yang boleh kita gunakan untuk menyelesaikan elemen array. Tetapi seperti yang kita akan lihat, ia mendapat perbezaan yang sangat asas dari jenis pemilihan, gelembung jenis, dan sisipan jenis yang membuat ia benar-benar cantik pandai. 

Idea asas di sebalik merge jenis adalah untuk menyusun tatasusunan yang lebih kecil dan kemudian menggabungkan mereka tatasusunan bersama-sama, atau bergabung mereka, kelak oleh itu name-- dalam usaha disusun. Cara yang bergabung apapun tidak ini adalah dengan menggunakan alat yang dipanggil rekursi, iaitu apa yang kita akan bercakap tentang tidak lama lagi, tetapi kita tidak benar-benar bercakap tentang lagi. 

Berikut adalah idea asas di sebalik jenis merge. Susun separuh kiri array, dengan andaian n lebih besar daripada 1. Dan apa yang saya maksudkan apabila saya mengatakan dengan andaian n lebih besar daripada 1 adalah, Saya rasa kita boleh bersetuju bahawa jika array hanya terdiri daripada satu unsur, ia disusun. Kita sebenarnya tidak perlu berbuat apa-apa kepadanya. Kami hanya dapat memberi diselesaikan. Ia hanya satu unsur. 

Jadi pseudokod, sekali lagi, menyusun separuh meninggalkan array, kemudian menyusun separuh kanan array, kemudian menggabungkan kedua-dua bahagian bersama-sama. Sekarang, sudah anda mungkin berfikir, ia jenis hanya bunyi seperti anda meletakkan off the-- anda sebenarnya tidak melakukan apa-apa. Anda katakan menyusun kiri separuh, menyusun separuh yang betul, tetapi anda tidak memberitahu saya bagaimana anda melakukannya. 

Tetapi ingat bahawa selagi array adalah elemen tunggal, kita boleh mengisytiharkan ia disusun. Maka kita hanya boleh menggabungkan mereka bersama-sama. Dan itulah sebenarnya idea asas di sebalik jenis merge, adalah untuk memecahkan ia ke bawah supaya tatasusunan anda mempunyai saiz satu. Dan kemudian anda membina semula dari sana. 

Bergabung apapun pasti algoritma rumit. Dan ia juga sedikit rumit untuk menggambarkan. Jadi diharapkan, visualisasi yang saya ada di sini akan membantu anda mengikuti bersama-sama. Dan saya akan cuba yang terbaik untuk menceritakan perkara dan meneruskan melalui ini lebih sedikit perlahan-lahan daripada yang lain hanya untuk mudah-mudahan mendapatkan kepala anda sekitar idea di sebalik jenis merge. 

Jadi kita mempunyai pelbagai yang sama dengan lain menyusun video algoritma jika anda telah melihat mereka, kelak pelbagai enam unsur. Dan kod pseudo kami di sini adalah jenis separuh kiri, menyusun separuh yang betul, menggabungkan kedua-dua bahagian bersama-sama. Jadi mari kita ini bata merah sangat gelap lokasi dan menyusun separuh meninggalkan daripadanya. 

Jadi buat masa ini, kita akan untuk mengabaikan hal-hal yang di sebelah kanan. Ia berada di sana, tetapi kami tidak pada langkah lagi. Kami tidak sama jenis yang separuh betul array. Kami pada jenis kiri separuh daripada array. Dan hanya demi menjadi lebih sedikit jelas, maka saya boleh merujuk apa langkah kita berada di, Saya akan menukar warna set ini kepada oren. Sekarang, kami masih bercakap tentang separuh kiri yang sama array asal. Tetapi saya berharap bahawa dengan mampu merujuk kepada warna-warna pelbagai barangan, ia akan membuat ia lebih sedikit jelas apa yang berlaku di sini. 

OK, jadi sekarang kita mempunyai tiga elemen tatasusunan. Bagaimana kita menyusun separuh kiri ini pelbagai, yang masih langkah ini? Kami cuba untuk menyusun kiri separuh daripada bata array-- merah separuh kiri yang Saya kini telah berwarna oren. 

Nah, kita boleh cuba dan mengulangi proses ini lagi. Oleh itu, kita masih dalam tengah cuba untuk menyelesaikan separuh kiri array penuh. Separuh kiri pelbagai, saya hanya akan sewenang-wenangnya membuat keputusan bahawa separuh kiri akan menjadi lebih kecil daripada separuh yang betul, kerana ini berlaku kepada terdiri daripada tiga elemen. 

Dan jadi saya akan mengatakan bahawa separuh kiri separuh kiri array hanya elemen lima. Lima, yang merupakan suatu elemen tunggal pelbagai, kita tahu bagaimana untuk menyelesaikannya. Dan sebagainya lima disusun. Kami hanya akan mengisytiharkan itu. Ia adalah pelbagai elemen. 

Jadi, sekarang kita telah disusun yang separuh kiri half-- sebelah kiri atau sebaliknya, kami telah disusun yang separuh kiri oren. Oleh sebab itu, untuk masih lengkap separuh kiri pelbagai keseluruhan ini, kita perlu menyusun separuh kanan oren, atau barangan ini. Bagaimana kita berbuat demikian? Nah, kita mempunyai pelbagai dua unsur. Oleh itu, kita boleh menyusun separuh sebelah kiri array, yang dua. Dua adalah elemen tunggal. Jadi ia disusun secara lalai. Kemudian kita boleh menyusun separuh kanan dengan bahagian array, satu. Itulah jenis secara lalai. 

Ketika ini merupakan kali pertama kita telah mencapai satu langkah merge. Kami telah menyiapkan, walaupun kami kini jenis bersarang down-- dan itulah jenis yang agak rumit perkara dengan rekursi adalah, anda perlu menyimpan anda mengetuai kira-kira di mana kita berada. Jadi kita ada semacam kiri separuh daripada bahagian oren. 

Dan sekarang, kita berada di tengah-tengah sorting separuh kanan bahagian oren. Dan dalam proses itu, kami kini kira-kira untuk berada di langkah, menggabungkan kedua-dua bahagian bersama-sama. Apabila kita melihat kedua-dua bahagian array, kita melihat dua dan satu. Unsur yang lebih kecil? One. 

Maka yang mana unsur yang lebih kecil? Nah, ia adalah dua atau apa-apa. Jadi ia adalah dua. Oleh sebab itu, hanya untuk sekali lagi bingkai di mana kita berada dalam konteks, kami telah disusun yang separuh kiri oren dan separuh kanan asalan. Saya tahu saya telah berubah warna sekali lagi, tetapi itulah di mana kita berada. Dan sebab itu saya melakukan ini adalah kerana proses ini adalah akan terus pergi, iterating ke bawah. Kami telah disusun kiri separuh daripada bekas oren dan separuh kanan bekas oren. 

Sekarang, kita perlu untuk menggabungkan mereka dua bahagian bersama-sama juga. Itulah langkah yang kita berada di. Oleh itu, kita mempertimbangkan semua unsur-unsur yang kini hijau, separuh kiri lokasi asal. Dan kita bergabung mereka menggunakan proses yang sama kita lakukan untuk menggabungkan dua dan satu hanya sebentar tadi. 

Separuh kiri, yang paling kecil elemen pada separuh kiri ialah lima. Elemen paling kecil pada separuh yang betul adalah satu. Yang mana satu adalah lebih kecil? One. 

Elemen paling kecil pada separuh kiri ialah lima. Elemen paling kecil pada separuh yang betul adalah dua. Apa yang paling kecil? Dua. Dan kemudian akhir sekali lima dan apa-apa, kita boleh mengatakan lima. 

OK, gambar begitu besar, mari kita berehat sebentar dan memikirkan di mana kita berada. Jika kita bermula dari awal-awal lagi, kita kini telah siap untuk array keseluruhan hanya satu langkah kod pseudo di sini. Kami yang disusun separuh kiri array. 

Ingat bahawa asal perintah berusia lima tahun, dua, satu. Dengan pergi melalui proses ini dan bersarang ke bawah dan mengulangi, berterusan untuk memecahkan masalah turun ke dalam bahagian yang lebih kecil dan lebih kecil, kita kini telah siap melangkah salah satu pseudokod kerana susunan permulaan keseluruhan. Kami disusun separuh kirinya. 

Jadi sekarang mari kita membekukan sana. Dan sekarang mari kita menyusun kanan separuh daripada lokasi asal. Dan kita akan berbuat demikian dengan melalui lelaran sama proses memecahkan perkara turun dan kemudian menggabungkan mereka bersama-sama. 

Jadi separuh kiri merah, atau separuh kiri daripada separuh kanan asal pelbagai, saya akan katakan adalah tiga. Sekali lagi, saya yang konsisten di sini. Jika anda mempunyai ganjil beberapa elemen, ia tidak benar-benar kira sama ada anda membuat satu kiri lebih kecil atau yang betul yang lebih kecil. 

Apa yang penting ialah bahawa setiap kali anda menghadapi masalah ini dalam menjalankan merge, anda perlu konsisten. Samada anda sentiasa perlu membuat pasukan yang ditinggalkan lebih kecil atau sentiasa perlu membuat sebelah kanan lebih kecil. Di sini, saya telah memilih untuk sentiasa membuat bahagian kiri lebih kecil apabila pelbagai saya, atau saya sub-pelbagai, adalah saiz ganjil. 

Tiga adalah elemen tunggal, dan oleh itu adalah disusun. Kami telah dimanfaatkan andaian bahawa sepanjang proses keseluruhan kami setakat ini. Jadi sekarang mari kita menyusun kanan separuh daripada separuh yang betul, atau separuh kanan merah. 

Sekali lagi, kita perlu berpecah ini ke bawah. Ini bukan satu pelbagai elemen. Kami tidak dapat memberi disusun. Dan jadi pertama, kita akan untuk menyusun separuh kiri. 

Separuh kiri adalah elemen tunggal, supaya ia semacam secara lalai. Kemudian kita akan menyusun kanan separuh, yang merupakan elemen tunggal. Ia disusun secara lalai. Dan sekarang, kita boleh menggabungkan kedua-dua bersama-sama. Empat adalah lebih kecil, dan maka enam adalah lebih kecil. 

Sekali lagi, apa yang telah kita lakukan pada ketika ini? Kami telah disusun kiri separuh daripada separuh betul. Atau akan kembali kepada asal warna yang berada di sana, kami telah disusun kiri separuh daripada merah lembut. Ia pada asalnya bata yang gelap merah dan kini ia merah yang lebih lembut, atau ia adalah merah yang lebih lembut. 

Dan kemudian kami telah disusun yang separuh kanan merah lembut. Sekarang, dengan baik, mereka hijau lagi, hanya kerana kita akan melalui satu proses. Dan kita perlu mengulangi lebih ini dan ke atas. 

Jadi sekarang kita boleh menggabungkan mereka dua bahagian bersama-sama. Dan itulah apa yang kita lakukan di sini. Jadi garis hitam hanya dibahagikan separuh kiri dan separuh kanan bahagian seperti ini. 

Kami membandingkan nilai terkecil di sebelah kiri array-- yang atau maafkan saya, yang paling kecil nilai separuh kiri kepada nilai yang paling kecil dari kanan separuh dan mendapati bahawa tiga adalah lebih kecil. Dan kini sedikit pengoptimuman, bukan? Ada sebenarnya apa-apa ditinggalkan di sebelah kiri. 

Tiada apa-apa baki di sebelah kiri, supaya kita boleh cekap hanya move-- kita boleh mengisytiharkan sepanjang ia sebenarnya disusun dan hanya jelujur ia pada, kerana tiada apa-apa lain untuk membandingkan terhadap. Dan kita tahu bahawa sebelah kanan sebelah kanan disusun. 

OK, jadi sekarang mari kita membekukan lagi dan memikirkan di mana kita berada dalam cerita. Dalam array secara keseluruhan, apa yang telah dicapai? Kami benar-benar telah mencapai kini beberapa langkah satu dan langkah dua. Kami disusun separuh kiri, dan kita disusun separuh betul. 

Oleh sebab itu, apa yang tinggal untuk kita untuk menggabungkan kedua-dua bahagian sekali. Oleh itu, kita bandingkan paling bernilai unsur setiap babak array seterusnya dan teruskan. Satu adalah kurang daripada tiga, jadi satu pergi. 

Dua adalah kurang daripada tiga, jadi dua pergi. Tiga adalah kurang daripada 5, jadi tiga pergi. Empat adalah kurang daripada 5, jadi empat pergi. Kemudian lima adalah kurang daripada enam, dan enam sahaja yang masih kekal. 

Sekarang, saya tahu, itu adalah banyak langkah-langkah. Dan kita telah meninggalkan banyak memori di belakangnya kami. Dan itulah apa yang mereka dataran kelabu. Dan ia mungkin merasa seperti itu mengambil banyak lebih lama daripada jenis kemasukan, gelembung jenis, atau jenis pemilihan. 

Tetapi sebenarnya, kerana banyak proses ini yang berlaku di time-- yang sama yang adalah sesuatu yang kita akan, sekali lagi, bercakap tentang apabila kita bercakap mengenai rekursi di masa depan yang video-- algoritma ini sebenarnya jelas asasnya yang berbeza daripada apa-apa kita lihat sebelum tetapi juga ketara lebih cekap. 

Kenapa begitu? Nah, dalam yang paling teruk senario kes, kami mempunyai untuk berpecah n unsur sehingga dan kemudian bergabung semula mereka. Tetapi apabila kita bergabung semula mereka, apa yang kita lakukan pada dasarnya dua kali ganda Saiz tatasusunan yang lebih kecil. Kami mempunyai sekumpulan satu elemen tatasusunan yang kita berkesan bergabung ke dalam dua tatasusunan unsur. Dan kemudian kita mengambil orang-orang dua tatasusunan elemen dan menggabungkan mereka bersama-sama ke empat tatasusunan elemen, dan sebagainya, dan sebagainya, dan sebagainya, sehingga kita mempunyai pelbagai n elemen tunggal. 

Tetapi berapa ramai doublings masa yang diambil untuk sampai ke n? Fikirkan kembali kepada contoh buku telefon. Berapa kali kita perlu air mata buku telefon pada separuh, berapa banyak lagi kali kita perlu air mata buku telefon pada separuh, jika saiz buku telefon dua kali ganda? Terdapat hanya satu, bukan? 

Jadi ada beberapa jenis unsur logaritma di sini. Tetapi kita juga masih perlu sekurang-kurangnya melihat semua n unsur-unsur. Jadi, dalam kes yang teruk, bergabung apapun berjalan dalam n log n. Kita perlu melihat semua n elemen, dan kita perlu menggabungkan mereka bersama-sama dalam log n set langkah-langkah. Dalam kes senario yang terbaik, array sempurna disusun. Itu yang besar. Tetapi berdasarkan algoritma yang kita ada di sini, kita masih perlu berpecah dan bergabung semula. Walaupun dalam kes ini, recombining adalah jenis tidak berkesan. Ia tidak diperlukan. Tetapi kita masih melalui keseluruhan proses juga. 

Jadi dalam kes ini, dan dalam kes paling teruk, algoritma ini berjalan dalam n log n masa. Bergabung apapun pasti agak lebih sukar daripada yang lain algoritma isihan utama kita telah bercakap tentang CS50 tetapi ketara lebih kuat. 

Dan jadi jika anda pernah mendapati kesempatan untuk memerlukannya atau menggunakannya untuk menyusun set data yang besar, mendapat kepala anda sekitar idea rekursi akan menjadi benar-benar kuat. Dan ia akan membuat anda program benar-benar jauh lebih efisien menggunakan bergabung apapun berbanding yang lain. Saya Doug Lloyd. Ini adalah CS50.