My first Magazine pemrograman-kompetitif-dasar | Page 56

5 Divide and Conquer
5 6 7
8 9
1 2 3
Gambar 5.13: Langkah 4: Bandingkan 5 dengan 8. Kita ambil 5 sebagai elemen selanjutnya
karena 5 ≤ 8
6 7
8 9
1 2 3 5
Gambar 5.14: Langkah 5: Bandingkan 6 dengan 8. Kita ambil 6 sebagai elemen selanjutnya
karena 6 ≤ 8
7
8 9
1 2 3 5 6
Gambar 5.15: Langkah 6: Bandingkan 7 dengan 8. Kita ambil 7 sebagai elemen selanjutnya
karena 7 ≤ 8
8 9
1 2 3 5 6 7
Gambar 5.16: Langkah 7: Ketika salah satu array telah habis, array yang masih bersisa tinggal
ditempelkan di akhir array gabungan.
1 2 3 5 6 7 8 9
Gambar 5.17: Proses penggabungan telah selesai. Array telah terurut.
Berapa kompleksitas proses ini? Misalkan kedua array terurut yang akan digabung adalah A
dan B. Pada setiap langkah, salah satu elemen dari A atau B dipindahkan ke dalam array gabungan.
Total terdapat |A| + |B| elemen yang dipindahkan, sehingga kompleksitasnya O(|A| + |B|).
46