Materi
Bagi-kuasai adalah strategi yang memecah masalah menjadi beberapa bagian sejenis yang lebih kecil, menyelesaikan tiap bagian secara rekursif, lalu menggabungkan hasilnya. Urut gabung (merge sort) adalah contoh paling terkenal: daftar dibelah dua sampai setiap bagian berisi satu data, karena daftar satu data pasti sudah urut, lalu bagian-bagian itu digabung kembali berpasangan.
Seluruh pekerjaan ada di langkah menggabung. Dua daftar yang masing-masing sudah urut dibaca dengan dua penunjuk dari depan. Di setiap langkah, data yang lebih kecil di antara dua penunjuk diambil dan penunjuknya maju. Begitu salah satu daftar habis, sisa daftar lainnya sudah urut dan tinggal disalin ke belakang. Menggabung dua daftar dengan total n data butuh paling banyak n langkah.
| Langkah | Kiri [3, 9] | Kanan [4, 5, 12] | Hasil |
|---|---|---|---|
| 1 | 3 dipilih | 4 | [3] |
| 2 | 9 | 4 dipilih | [3, 4] |
| 3 | 9 | 5 dipilih | [3, 4, 5] |
| 4 | 9 dipilih | 12 | [3, 4, 5, 9] |
| sisa | habis | 12 disalin | [3, 4, 5, 9, 12] |
Biayanya dihitung per tingkat. Setiap tingkat pembelahan menggabungkan seluruh n data sekali, dan banyaknya tingkat adalah berapa kali n bisa dibagi dua sampai tersisa 1, yaitu sekitar log₂ n. Totalnya O(n log n). Untuk sejuta data itu sekitar 20 juta langkah, jauh di bawah cara yang membandingkan setiap pasangan data. Urut gabung juga stabil bila data yang sama diambil dari daftar kiri lebih dulu, sifat yang sama yang dijamin sorted() di Python.
def belah(data):
tengah = len(data) // 2
return data[:tengah], data[tengah:]
# belah([8, 1, 6, 2, 7]) -> ([8, 1], [6, 2, 7])
