PengurutanMenengahFase D–FE1E5

Merge Sort

Merge Sort adalah algoritma pengurutan divide-and-conquer yang membagi array menjadi dua bagian secara rekursif hingga tersisa satu elemen, lalu menggabungkan (merge) kembali bagian-bagian tersebut dalam urutan terurut. Proses penggabungan selalu mengambil elemen terkecil dari kepala kedua bagian. Visualisasi menampilkan batang-batang yang dipecah menjadi setengah lalu digabung kembali hingga seluruh array terurut.

Contoh kasus

Mengurutkan daftar besar transaksi atau file log secara efisien dan stabil di sistem basis data.

Silabus

Membagi array jadi dua terus-menerus sampai satu elemen, lalu menggabungkannya kembali secara terurut (divide and conquer).

Tujuan Belajar

·Memahami strategi divide and conquer pada pengurutan
·Menjelaskan cara menggabungkan dua bagian terurut jadi satu
·Menerapkan Merge Sort untuk data besar yang butuh stabil

Cara Kerja

·Bagi array menjadi dua bagian secara berulang
·Terus bagi hingga tiap bagian tinggal satu elemen
·Gabungkan dua bagian dengan mengambil kepala terkecil dulu
·Salin sisa elemen bagian yang belum habis
·Naik bertahap hingga seluruh array tergabung terurut

Prasyarat

·Array
·Rekursi

Contoh Nyata

·Menggabungkan file log terurut dari beberapa server sekaligus
·Mengurutkan daftar besar transaksi Shopee secara stabil

Kompleksitas O(n log n)