My first Magazine pemrograman-kompetitif-dasar | Page 55

5.2 Studi Kasus 1: Merge Sort
5.2.2
Menggabungkan Dua Array yang Terurut
Bagaimana cara menggabungkan dua array yang telah terurut menjadi sebuah array yang
terurut?
Observasi: elemen terkecil (terkiri) dari array gabungan pasti merupakan salah satu dari
elemen terkecil (terkiri) di antara kedua array . Dengan kata lain, kita selalu mengambil nilai
terkecil dari kedua array yang belum dimasukkan ke array gabungan sebagai elemen selanjutnya
di array gabungan.
2 5 6 7
1 3 8 9
Gambar 5.9: Diberikan 2 buah array yang sudah terurut, kita ingin menggabungkannya menjadi
satu array yang terurut.
Sebagai contoh, diberikan 2 buah array terurut [2, 5, 6, 7] dan [1, 3, 8, 9]. Untuk menggabung-
kan keduanya, kita akan membandingkan elemen terkecil yang belum dipilih dari masing-masing
array dan memilih yang terkecil. Gambar 5.10 hingga Gambar 5.17 mengilustrasikan proses
penggabungan dari awal sampai akhir.
2 5 6 7
1 3 8 9
Gambar 5.10: Langkah 1: Bandingkan 1 dan 2. Karena 1 ≤ 2, kita ambil 1 sebagai elemen
pertama di array gabungan.
Ulangi hal serupa sampai salah satu atau kedua array habis.
2 5 6 7
3 8 9
1
Gambar 5.11: Langkah 2: Bandingkan 2 dengan 3. Kita ambil 2 sebagai elemen selanjutnya
karena 2 ≤ 3
5 6 7
3 8 9
1 2
Gambar 5.12: Langkah 3: Bandingkan 5 dengan 3. Kita ambil 3 sebagai elemen selanjutnya
karena 3 ≤ 5
45