Divide and conquer dan jejak merge sort
Pecah masalah, gabungkan hasil, dan hitung biaya per level.
dasar #merge sort
SlideDivide and ConquerRekursif, Relasi Rekurens dan Proof of The Master Theorem
Yang akan kamu pahami
Kenali base case, langkah divide, dan langkah combine.
Konsep inti
Merge sort membagi array menjadi dua bagian, mengurutkan masing-masing, lalu menggabungkannya dengan mengambil elemen terkecil di kepala dua daftar. Untuk n pangkat dua, T(n) = 2T(n/2) + Θ(n). Ada log₂(n) level penggabungan dan total kerja linear di tiap level.
Coba langkahnya
Urutkan [7, 2, 5, 1].
| 0 | 1 | 2 | 3 | |
|---|---|---|---|---|
| Kiri | 7 | 2 | · | · |
| Kanan | 5 | 1 | · | · |
| Hasil | · | · | · | · |
Cek pemahaman
Latihan UTS & UAS
- UTS 2026 · No. 1bTelusuri pembagian dan penggabungan merge sort.
- UTS 2025 · No. 2Tulis recurrence dan jelaskan biaya tiap level.