Merge sort adalah salah satu algoritma pengurutan yang paling efisien dan banyak digunakan dalam ilmu komputer. Ini termasuk dalam kategori algoritma membagi-dan-menaklukkan, di mana masalahnya dipecah menjadi submasalah yang lebih kecil, diselesaikan secara rekursif, dan kemudian digabungkan untuk mendapatkan hasil akhir. Pengurutan gabungan, yang dikenal karena kinerjanya yang stabil dan dapat diprediksi, telah menemukan berbagai aplikasi dalam menyortir kumpulan data besar, menjadikannya alat yang penting bagi pengembang dan analis data.<\/p>\n
Konsep Pengurutan gabungan dimulai pada tahun 1940-an dan pertama kali diusulkan oleh John von Neumann pada tahun 1945. Namun, baru pada tahun 1948 John von Neumann dan Stanislaw Ulam memformalkan algoritme dan menetapkan prinsip-prinsip dasarnya. Pekerjaan mereka pada Merge sort terutama terkait dengan penyortiran kumpulan data besar secara efisien dan memainkan peran penting dalam meletakkan dasar bagi perkembangan masa depan dalam ilmu komputer dan desain algoritma.<\/p>\n
Pengurutan gabungan beroperasi berdasarkan prinsip membagi daftar yang tidak diurutkan menjadi subdaftar yang lebih kecil, mengurutkan subdaftar tersebut, dan kemudian menggabungkannya kembali untuk mendapatkan daftar yang diurutkan sepenuhnya. Prosesnya dapat dipecah menjadi langkah-langkah berikut:<\/p>\n
Membagi<\/strong>: Daftar yang tidak disortir dibagi menjadi dua bagian yang sama, berulang kali, hingga setiap subdaftar berisi satu elemen.<\/p>\n<\/li>\n Menaklukkan<\/strong>: Setiap elemen individu dianggap sebagai sublist yang diurutkan.<\/p>\n<\/li>\n Menggabungkan<\/strong>: Subdaftar yang diurutkan kemudian digabungkan, dan elemen-elemennya dibandingkan dan digabungkan sedemikian rupa sehingga menghasilkan daftar akhir yang diurutkan.<\/p>\n<\/li>\n<\/ol>\n Pengurutan gabungan menunjukkan kompleksitas waktu O(n log n), di mana \u201cn\u201d adalah jumlah elemen dalam daftar. Hal ini membuat pengurutan gabungan jauh lebih cepat dibandingkan algoritma pengurutan lain yang umum digunakan, seperti pengurutan gelembung dan pengurutan penyisipan, terutama ketika berhadapan dengan kumpulan data yang besar.<\/p>\n Pengurutan gabungan diimplementasikan menggunakan pendekatan rekursif. Fungsi inti membagi daftar masukan menjadi dua bagian, dan masing-masing bagian diurutkan secara independen menggunakan pendekatan rekursif yang sama. Setelah masing-masing bagian diurutkan, langkah penggabungan menggabungkannya ke dalam satu daftar yang diurutkan. Proses penggabungan difasilitasi oleh dua petunjuk utama yang membandingkan elemen dari kedua bagian dan menggabungkannya menjadi hasil akhir.<\/p>\n Pengurutan gabungan menawarkan beberapa fitur utama yang menjadikannya pilihan populer untuk tugas pengurutan:<\/p>\n Stabilitas<\/strong>: Pengurutan gabungan adalah algoritme pengurutan yang stabil, artinya elemen yang sama mempertahankan urutan relatifnya dalam keluaran yang diurutkan seperti pada daftar asli yang tidak diurutkan.<\/p>\n<\/li>\n Kinerja yang dapat diprediksi<\/strong>: Kompleksitas waktu pengurutan gabungan sebesar O(n log n) memastikan kinerja yang konsisten dan efisien, sehingga cocok untuk kumpulan data besar.<\/p>\n<\/li>\n Cocok untuk daftar tertaut<\/strong>: Tidak seperti beberapa algoritme pengurutan lainnya, Pengurutan gabungan memiliki kinerja yang sama baiknya pada daftar tertaut karena pola akses berurutannya, yang meminimalkan overhead akses acak.<\/p>\n<\/li>\n Mudah diterapkan<\/strong>: Sifat rekursif penggabungan pengurutan dan proses penggabungan yang mudah membuatnya relatif mudah diimplementasikan dalam berbagai bahasa pemrograman.<\/p>\n<\/li>\n<\/ol>\n Ada dua varian utama dari Merge sort:<\/p>\n Pengurutan Penggabungan Top-Down<\/strong>: Ini adalah implementasi klasik dari Pengurutan gabungan yang menggunakan rekursi untuk membagi daftar dan mengurutkan subdaftar. Ini dimulai dengan seluruh daftar dan secara rekursif membaginya menjadi subdaftar yang lebih kecil hingga kasus dasar (daftar elemen tunggal) tercapai. Sublist tersebut kemudian digabungkan kembali menjadi daftar yang diurutkan.<\/p>\n<\/li>\n Pengurutan Penggabungan dari Bawah ke Atas<\/strong>: Dalam varian ini, algoritme membagi daftar secara berulang menjadi subdaftar dengan ukuran tetap dan menggabungkannya secara bottom-up. Proses berlanjut hingga seluruh daftar diurutkan.<\/p>\n<\/li>\n<\/ol>\n Mari kita bandingkan dua jenis Merge sort dalam sebuah tabel:<\/p>\nStruktur internal Pengurutan Penggabungan: Cara kerja Pengurutan Penggabungan<\/h2>\n
Analisis fitur utama dari Merge sort<\/h2>\n
\n
Jenis-jenis Penggabungan<\/h2>\n
\n