[MUSIC PLAYING] 

Doug LLOYD: OK, jadi penggabungan semacam belum algoritma lain yang bisa kita gunakan untuk memilah elemen array. Tapi seperti yang kita akan lihat, itu punya perbedaan yang sangat mendasar dari pemilihan semacam, bubble macam, dan insertion sort yang membuatnya benar-benar cukup pintar. 

Ide dasar di balik merge semacam ini untuk mengurutkan array yang lebih kecil dan kemudian menggabungkan mereka array bersama-sama, atau menggabungkan them-- maka name-- untuk disortir. Cara menggabungkan semacam tidak ini adalah dengan memanfaatkan alat disebut rekursi, yang adalah apa yang kita akan berbicara tentang segera, tapi kita belum benar-benar berbicara tentang belum. 

Berikut ide dasar di balik merge sort. Urutkan kiri setengah dari array, asumsi n lebih besar dari 1. Dan apa yang saya maksud ketika saya mengatakan asumsi n lebih besar dari 1 adalah, Saya pikir kita bisa setuju bahwa jika sebuah array hanya terdiri dari satu elemen, itu diurutkan. Kami tidak benar-benar perlu melakukan apapun untuk itu. Kami hanya dapat mendeklarasikan akan diurutkan. Ini hanya satu elemen. 

Jadi pseudocode, sekali lagi, adalah mengurutkan setengah kiri dari array, kemudian mengurutkan bagian kanan array, kemudian menggabungkan dua bagian bersama-sama. Sekarang, Anda mungkin sudah berpikir, itu jenis hanya Kedengarannya seperti Anda menunda the-- Anda tidak benar-benar melakukan apa-apa. Anda mengatakan menyortir kiri setengah, mengurutkan bagian kanan, tapi kau tidak mengatakan saya bagaimana Anda melakukannya. 

Tapi ingat bahwa selama array adalah elemen tunggal, kita dapat mendeklarasikan diurutkan. Maka kita bisa menggabungkan mereka bersama-sama. Dan itulah sebenarnya Ide dasar di balik semacam penggabungan, adalah untuk memecahnya sehingga array Anda adalah ukuran satu. Dan kemudian Anda kembali dari sana. 

Menggabungkan semacam pasti algoritma yang rumit. Dan itu juga sedikit rumit untuk memvisualisasikan. Jadi mudah-mudahan, visualisasi yang saya miliki di sini akan membantu Anda mengikuti bersama. Dan aku akan mencoba yang terbaik untuk menceritakan hal-hal dan melanjutkan melalui ini lebih sedikit lambat dari yang lain hanya untuk mudah-mudahan mendapatkan kepala Anda sekitar ide dibalik merge sort. 

Jadi kita memiliki array sama dengan video algoritma sorting lainnya jika Anda pernah melihat them-- array enam elemen. Dan kode pseudo kami di sini adalah semacam kiri setengah, mengurutkan bagian kanan, menggabungkan dua bagian bersama-sama. Jadi mari kita bata merah ini sangat gelap array dan mengurutkan setengah kiri itu. 

Jadi untuk saat ini, kita akan mengabaikan hal-hal di sebelah kanan. Itu ada, tapi kami tidak pada langkah belum. Kami tidak di semacam itu kanan setengah dari array. Kami berada di semacam kiri setengah dari array. Dan hanya demi menjadi sedikit lebih jelas, jadi saya dapat merujuk apa langkah kita berada di, Aku akan mengganti warna set ini untuk oranye. Sekarang, kita masih berbicara tentang kiri setengah sama array asli. Tapi aku berharap bahwa dengan mampu mengacu pada warna dari berbagai item, itu akan membuatnya sedikit lebih jelas apa yang terjadi di sini. 

OK, jadi sekarang kita memiliki tiga elemen array. Bagaimana kita mengurutkan setengah kiri ini array, yang masih langkah ini? Kami mencoba untuk memilah kiri setengah dari bata merah array-- kiri setengah dari yang Saya sekarang sudah berwarna oranye. 

Nah, kita bisa mencoba dan ulangi proses ini lagi. Jadi kita masih di tengah berusaha untuk menyortir kiri setengah dari array penuh. Kiri setengah dari array, aku hanya akan untuk sewenang-wenang memutuskan bahwa setengah kiri akan lebih kecil dari bagian kanan, karena hal ini terjadi pada terdiri dari tiga elemen. 

Dan jadi saya akan mengatakan bahwa kiri setengah dari kiri setengah array hanya elemen lima. Lima, menjadi satu elemen array, kita tahu bagaimana mengatasinya. Dan lima diurutkan. Kami hanya akan menyatakan bahwa. Ini array elemen tunggal. 

Jadi sekarang kami telah diurutkan kiri setengah dari half-- kiri atau lebih tepatnya, kami telah diurutkan kiri setengah dari jeruk. Jadi sekarang, untuk masih lengkap kiri setengah array keseluruhan itu, kita perlu memilah bagian kanan dari jeruk, atau hal-hal ini. Bagaimana kita melakukannya? Nah, kita memiliki array dua elemen. Jadi kita dapat menyusun setengah kiri dari array, yang merupakan dua. Dua adalah elemen tunggal. Jadi itu diurutkan secara default. Kemudian kita bisa memilah bagian kanan yang bagian dari array, satu. Itu semacam secara default. 

Ini adalah pertama kalinya sekarang kami telah mencapai langkah penggabungan. Kami telah selesai, meskipun kita sekarang jenis bersarang down-- dan itu semacam rumit Hal dengan rekursi adalah, Anda perlu menjaga Anda kepala tentang di mana kita berada. Jadi kita sudah semacam kiri setengah dari porsi jeruk. 

Dan sekarang, kita berada di tengah-tengah menyortir kanan setengah dari porsi jeruk. Dan dalam proses itu, kita sekarang akan berada di langkah, menggabungkan dua bagian bersama-sama. Ketika kita melihat dua bagian dari array, kita melihat dua dan satu. Yang elemen lebih kecil? Satu. 

Kemudian yang elemen lebih kecil? Nah, itu dua atau tidak. Jadi dua. Jadi sekarang, hanya untuk membingkai lagi di mana kita berada dalam konteks, kami telah diurutkan kiri setengah dari jeruk dan bagian kanan asal. Aku tahu aku sudah berubah warna lagi, tapi itu di mana kita berada. Dan alasan saya melakukan ini karena proses ini akan terus, iterasi turun. Kami telah diurutkan kiri setengah dari mantan orange dan kanan setengah dari mantan oranye. 

Sekarang, kita perlu menggabungkan mereka dua bagian bersama-sama juga. Itulah langkah kami di. Jadi kita mempertimbangkan semua elemen yang sekarang hijau, kiri setengah dari array asli. Dan kami gabungkan menggunakan proses yang sama kami lakukan untuk penggabungan dua dan satu hanya beberapa saat yang lalu. 

Kiri setengah, yang terkecil elemen pada kiri setengah lima. Elemen terkecil pada bagian kanan adalah salah satu. Mana yang lebih kecil? Satu. 

Elemen terkecil pada kiri setengah lima. Elemen terkecil pada kanan setengah dua. Apa yang terkecil? Dua. Dan kemudian terakhir lima dan apa-apa, kita dapat mengatakan lima. 

OK, gambar begitu besar, mari kita istirahat untuk kedua dan mencari tahu di mana kita berada. Jika kita mulai dari awal, kami sekarang telah diselesaikan untuk array secara keseluruhan hanya satu langkah dari kode pseudocode sini. Kami telah diurutkan kiri setengah dari array. 

Ingat bahwa asli Agar lima, dua, satu. Dengan pergi melalui proses ini dan bersarang ke bawah dan mengulangi, terus memecahkan masalah ke dalam bagian yang lebih kecil dan lebih kecil, kita sekarang telah menyelesaikan langkah salah pseudocode untuk seluruh array awal. Kami telah diurutkan setengah kiri. 

Jadi sekarang mari kita membeku di sana. Dan sekarang mari kita mengurutkan kanan setengah dari array asli. Dan kita akan melakukannya dengan akan melalui iterasi yang sama Proses melanggar segalanya dan kemudian menggabungkan mereka bersama-sama. 

Jadi kiri setengah dari merah, atau setengah kiri dari kanan setengah dari aslinya array, saya akan katakan adalah tiga. Sekali lagi, aku bersikap konsisten di sini. Jika Anda memiliki aneh jumlah elemen, itu tidak benar-benar peduli apakah Anda membuat satu kiri lebih kecil atau hak yang lebih kecil. 

Yang penting adalah bahwa setiap kali Anda menghadapi masalah ini dalam melakukan gabungan, Anda harus konsisten. Anda juga harus selalu membuat sisi kiri lebih kecil atau selalu perlu membuat sisi kanan yang lebih kecil. Di sini, saya telah memilih untuk selalu membuat sisi kiri lebih kecil ketika array saya, atau saya sub-array, adalah ukuran yang aneh. 

Tiga adalah satu elemen, dan karena itu diurutkan. Kami telah memanfaatkan asumsi bahwa sepanjang seluruh proses kami sejauh ini. Jadi sekarang mari kita mengurutkan kanan setengah dari setengah benar, atau bagian kanan merah. 

Sekali lagi, kita perlu untuk membagi ini turun. Ini bukan array elemen tunggal. Kita tidak bisa menyatakan itu diurutkan. Dan jadi pertama, kita akan memilah kiri setengah. 

Setengah kiri adalah elemen tunggal, jadi semacam secara default. Kemudian kita akan mengurutkan kanan setengah, yang merupakan elemen tunggal. Ini diurutkan secara default. Dan sekarang, kita bisa menggabungkan dua bersama-sama. Empat lebih kecil, dan kemudian enam lebih kecil. 

Sekali lagi, apa yang telah kita lakukan pada saat ini? Kami telah diurutkan kiri setengah dari setengah benar. Atau akan kembali ke aslinya warna yang ada, kami telah diurutkan kiri setengah dari merah lembut. Awalnya batu bata gelap merah dan sekarang itu lebih lembut merah, atau itu merah lembut. 

Dan kemudian kami telah diurutkan setengah kanan merah lembut. Sekarang, baik, mereka hijau lagi, hanya karena kita akan melalui sebuah proses. Dan kita harus mengulang ini berulang. 

Jadi sekarang kita bisa menggabungkan mereka dua bagian bersama-sama. Dan itulah yang kami lakukan di sini. Jadi garis hitam hanya dibagi kiri setengah dan kanan setengah dari semacam bagian ini. 

Kami membandingkan nilai terkecil di sisi kiri array-- yang atau permisi, terkecil nilai kiri setengah dengan nilai terkecil dari kanan setengah dan menemukan bahwa tiga lebih kecil. Dan sekarang sedikit optimasi, kan? Sebenarnya ada apa-apa kiri di sisi kiri. 

Tidak ada yang tersisa di sisi kiri, sehingga kita bisa efisien hanya move-- kita dapat mendeklarasikan sisanya sebenarnya diurutkan dan hanya taktik itu pada, karena tidak ada lain untuk membandingkan terhadap. Dan kita tahu bahwa sisi kanan dari sisi kanan diurutkan. 

OK, jadi sekarang mari kita membekukan lagi dan mencari tahu di mana kita berada dalam cerita. Dalam array secara keseluruhan, apa yang telah kita capai? Kami benar-benar telah mencapai sekarang langkah satu dan langkah dua. Kami diurutkan kiri setengah, dan kami diurutkan kanan setengah. 

Jadi sekarang, semua yang tersisa adalah bagi kita untuk menggabungkan dua bagian bersama-sama. Jadi kita membandingkan termurah dihargai unsur masing-masing setengah dari array pada gilirannya dan melanjutkan. Salah satunya adalah kurang dari tiga, jadi satu pergi. 

Dua kurang dari tiga, sehingga dua pergi. Tiga kurang dari 5, sehingga tiga pergi. Empat kurang dari 5, sehingga empat pergi. Kemudian lima kurang dari enam, dan enam adalah semua yang tersisa. 

Sekarang, saya tahu, itu banyak langkah-langkah. Dan kami telah meninggalkan banyak memori di bangun kami. Dan itulah yang mereka kotak abu-abu. Dan mungkin merasa seperti itu mengambil banyak lebih lama dari insertion sort, bubble semacam, atau semacam seleksi. 

Tapi sebenarnya, karena banyak proses ini yang terjadi di time-- sama yang merupakan sesuatu yang kita akan, lagi, berbicara tentang ketika kita berbicara tentang rekursi di masa depan video-- algoritma ini benar-benar jelas adalah fundamental yang berbeda dari apa pun kita telah melihat sebelumnya tetapi juga secara signifikan lebih hemat. 

Kenapa itu? Nah, di terburuk skenario, kita memiliki untuk membagi n elemen up dan kemudian bergabung kembali mereka. Tetapi ketika kita bergabung mereka, apa yang kita lakukan pada dasarnya menggandakan ukuran array yang lebih kecil. Kami memiliki sekelompok satu elemen array yang kita efektif menggabungkan ke dua array elemen. Dan kemudian kita mengambil mereka dua array elemen dan menggabungkannya ke empat elemen array, dan sebagainya, dan seterusnya, dan seterusnya, sampai kita memiliki array elemen n tunggal. 

Tapi berapa banyak doubling yang dibutuhkan untuk sampai ke n? Pikirkan kembali ke contoh buku telepon. Berapa kali kita harus merobek buku telepon di setengah, berapa banyak lagi kali kita harus merobek buku telepon dalam setengah, jika ukuran buku telepon dua kali lipat? Hanya ada satu, kan? 

Jadi ada semacam elemen logaritmik sini. Tapi kami juga masih harus setidaknya melihat semua elemen n. Jadi dalam skenario terburuk, menggabungkan semacam berjalan di n log n. Kita harus melihat semua elemen n, dan kita harus menggabungkan mereka bersama-sama dalam log n set langkah. Dalam skenario kasus terbaik, array sempurna diurutkan. Itu bagus. Tetapi berdasarkan algoritma yang kita miliki di sini, kita masih harus membagi dan bergabung kembali. Meskipun dalam hal ini, recombining adalah jenis yang tidak efektif. Hal ini tidak diperlukan. Tapi kami masih pergi melalui seluruh proses pula. 

Jadi dalam kasus terbaik dan dalam kasus terburuk, algoritma ini berjalan di n log n waktu. Menggabungkan semacam pasti sedikit lebih sulit dari algoritma pemilahan utama lainnya kita bicarakan CS50 tetapi substansial lebih kuat. 

Dan jadi jika Anda pernah menemukan kesempatan untuk membutuhkannya atau menggunakannya untuk mengurutkan set data yang besar, mendapatkan kepala Anda sekitar gagasan rekursi akan menjadi benar-benar kuat. Dan itu akan membuat Anda program benar-benar jauh lebih efisien menggunakan menggabungkan semacam dibandingkan apa pun. Aku Doug Lloyd. Ini adalah CS50.