Kompleksitas Waktu dan Ruang

Kompleksitas Waktu:

• Kasus Terbaik, Rata-rata, dan Terburuk: O(n log n)
  • Array dibagi menjadi dua bagian sekitar log n kali, dan setiap tingkat melakukan pekerjaan O(n) untuk menggabungkan. Waktu eksekusi tidak bergantung pada urutan input.

Kompleksitas Ruang:

• O(n)
  • Tidak seperti pengurutan di tempat, Merge Sort membuat array baru saat menggabungkan, sehingga memerlukan memori tambahan yang sebanding dengan ukuran input.

Ringkasan:

• Merge Sort cepat dan konsisten: O(n log n) dalam setiap kasus.
• Algoritma ini stabil, sehingga elemen yang sama mempertahankan urutannya.
• Komprominya adalah penggunaan memori tambahan O(n) untuk penggabungan.