Motivasi

Merge Sort membagi masalah menjadi submasalah yang lebih kecil, menyelesaikan masing-masing, lalu menggabungkan hasilnya. Langkah penggabungan itu, yaitu menggabungkan dua list yang sudah diurutkan, merupakan inti algoritma ini.

Mengapa belajar Merge Sort?

• Cepat dan dapat diprediksi: algoritma ini berjalan dalam waktu O(n log n) pada kasus terbaik, rata-rata, dan terburuk.
• Stabil: elemen yang nilainya sama mempertahankan urutan relatif semula.
• Cocok untuk data berukuran besar: algoritma ini bekerja dengan baik saat data tidak muat di memori (pengurutan eksternal) dan untuk linked list.
• Bagi dan taklukkan: algoritma ini mengajarkan pola yang digunakan dalam banyak algoritma tingkat lanjut.