Merge sort
Merge sort mengubah satu masalah sulit menjadi banyak masalah mudah: dua daftar terurut mudah digabung menjadi satu. Bagi daftar menjadi dua sampai setiap potongan tinggal satu nilai, lalu gabungkan potongan-potongan itu kembali. Ini algoritma divide and conquer klasik, dan waktunya n log n apa pun masukannya.
Idenya
Penggabungan adalah bagian yang mudah. Diberikan dua daftar yang masing-masing terurut, bandingkan nilai pertamanya dan ambil yang lebih kecil. Bandingkan nilai pertama yang baru dan ambil lagi yang lebih kecil. Jika satu daftar habis, tambahkan sisa daftar lainnya. Setiap langkah mengambil satu nilai, jadi menggabungkan dua daftar dengan panjang total m butuh paling banyak m − 1 perbandingan. Merge sort memakai itu untuk mengurutkan: bagi daftar menjadi dua, urutkan setiap paruh dengan merge sort, lalu gabungkan kedua paruh.
Contoh
Ambil 5, 1, 4, 2, 8. Bagi menjadi 5, 1 dan 4, 2, 8. Paruh pertama dibagi menjadi 5 dan 1, yang digabung menjadi 1, 5. Paruh kedua dibagi menjadi 4 dan 2, 8; 2, 8 digabung dari 2 dan 8, lalu digabung dengan 4 menjadi 2, 4, 8. Terakhir 1, 5 dan 2, 4, 8 digabung: 1, lalu 2, lalu 4, lalu 5, dan 8 tersisa. Itu 8 perbandingan, 12 penulisan, dan 4 penggabungan.
Mengapa n log n
Setiap pembagian membelah potongan menjadi dua, jadi setelah sekitar log₂ n tingkat setiap potongan tinggal satu nilai. Saat naik kembali, setiap tingkat penggabungan menangani setiap nilai sekali, yaitu n penulisan dan kurang dari n perbandingan per tingkat. Totalnya sekitar n log₂ n. Untuk 40 nilai, pengurutan melakukan 216 penulisan dan paling banyak 177 perbandingan; bubble sort bisa butuh 780 perbandingan untuk daftar yang sama. Urutan masukan juga jauh kurang berpengaruh dibanding pada pengurutan itu: untuk 40 nilai, daftar terurut butuh 100 perbandingan, daftar terbalik 116, dan daftar acak sekitar 160.
Buffer dan stabilitas
Untuk menggabungkan dua paruh yang bersebelahan di daftar, cara biasa adalah menyalinnya ke buffer dan menuliskannya kembali secara berurutan. Aplikasi ini menampilkan buffer itu sebagai baris batang kedua. Dibutuhkan memori tambahan sebanyak daftar, dan itulah biaya utama merge sort. Sebagai gantinya, pengurutannya stabil: jika dua nilai terdepan sama, yang dari paruh kiri didahulukan, sehingga nilai yang sama tetap pada urutannya. Stabilitas penting saat mengurutkan data menurut satu kolom lalu kolom lain.
Sejarah dan penggunaan
John von Neumann menjelaskan merge sort pada 1945, menjadikannya salah satu algoritma pertama yang ditulis untuk komputer program tersimpan. Karena membaca dan menulis data dalam rangkaian panjang, merge sort menjadi metode standar untuk mengurutkan data di pita magnetik dan masih dipakai untuk file yang terlalu besar untuk memori. Timsort, yang dipakai Python dan Java untuk objek, adalah merge sort yang lebih dulu mencari rangkaian yang sudah terurut dan memakai insertion sort untuk potongan pendek.
Jelajahi
Buka aplikasinya dan tekan Langkah. Bagian daftar yang diarsir sedang dibagi atau digabung, dan garis putus-putus menandai bagian tengah. Saat penggabungan dimulai, kedua paruh turun ke baris buffer; dua nilai terdepan dibandingkan, dan yang lebih kecil naik kembali. Perhatikan penghitungnya: jumlah penulisan sama untuk setiap daftar dengan panjang yang sama, sedangkan perbandingan paling sedikit untuk daftar terurut atau terbalik dan paling banyak untuk daftar acak, tetapi tidak pernah lebih dari sekitar n log₂ n.
Pertanyaan yang sering diajukan
Berapa kompleksitas waktu merge sort?
O(n log n) pada kasus terbaik, rata-rata, dan terburuk. Versi biasanya butuh memori tambahan O(n) untuk buffer.
Apa beda merge sort dan quicksort?
Keduanya membagi daftar dan mengurutkan bagian-bagiannya. Merge sort membagi di tengah tanpa melihat nilainya dan bekerja saat menggabungkan; quicksort bekerja saat membagi, dengan memindahkan nilai di sekitar pivot, dan tidak butuh penggabungan. Quicksort mengurutkan di tempat dan sering lebih cepat dalam praktik, tetapi bisa melambat hingga n² pada masukan yang buruk dan tidak stabil. Merge sort selalu n log n dan stabil.
Apa itu merge sort bottom-up?
Versi tanpa rekursi: pertama gabungkan nilai tunggal yang bersebelahan menjadi pasangan, lalu pasangan menjadi kelompok empat, dan seterusnya, sehingga panjangnya berlipat dua di setiap tahap. Kerjanya sama dengan versi top-down yang ditampilkan di sini.
Apakah merge sort stabil?
Ya, selama nilai yang seri diambil dari paruh kiri lebih dulu, seperti yang dilakukan aplikasi ini.
Siap mencobanya?
Buka PictorX di browser Anda — tanpa instalasi, tanpa kartu kredit untuk memulai.
Coba merge sort