Prof. Dra. Kiki Ariyanti Sugeng, M.Si., Ph.D.

Video ini membahas contoh penerapan Merge Sort dalam Matematika Diskrit dengan teknik perhitungan lanjutan. Merge Sort digunakan untuk mengurutkan daftar dengan jumlah elemen genap, membaginya menjadi dua, dan menggabungkan hasil urutannya dengan sedikit perbandingan. Algoritma Rekursif Merge Sortnya diilustrasikan melalui contoh dua daftar yang diurutkan. Proses penggabungan dua daftar terurut dilakukan dengan membandingkan elemen terkecil dari masing-masing daftar. Langkah ini diulang hingga semua elemen terurut.

Contoh yang berikutnya adalah Merge Sort, jadi ini sudah pernah dibahas sebelumnya

dan kita lihat bahwa kita punya satu barisan atau daftar yang mau diurut

banyaknya elemen itu n-nya genap, kalau n-nya genap itu dibagi dua persis n per dua

dan kemudian kita menggunakan kurang dari n perbandingan

untuk menyatukan hasil urutan dari masing-masing daftar n per dua

sehingga kita akan punya di sini untuk perbandingan dilakukan untuk n elemen kurang dari mn

nanti kita akan dapat mn-nya adalah dua kali mn per dua ditambah n

nah idenya ini algoritmanya untuk Rekursif Merge Sortnya

kita punya dua daftar atau dua list isinya 2356 dan 14

ilustrasi tabel disini kita bisa gambarkan dengan gambar

karena kita mau cari bilangan yang terkecil ke terbesar

jadi kita lihat dulu yang terkecil disebelah kiri dalam hal ini dua

sama terkecil yang disebelah kanan ini lebih kecil mana

karena kita mau sortingnya jadi harus mulai dari yang paling kecil

karena disini satu disini kita lihat ini satu lebih kecil dari dua

berarti kita masukkan di dalam list si satu ini

sekarang kita tinggal bandingkan 2356 satunya udah diambil jadi dengan empat

kita bandingkan dua yang paling kecil disebelah kiri sama empat

ternyata dua lebih kecil berarti dua ini kita masukkan ke dalam listnya

tadi udah ada satu kita masukkan dua ini disini satu dua

yang sebelah kiri tinggal 356 kita bandingkan dengan empat

tiga ini lebih kecil dari empat berarti tiga kita masukkan ke listnya

ini dicoret sekarang tiganya udah diambil berarti disini tinggal 56 sama empat

kemudian kita bandingkan ternyata empat lebih kecil jadi empat yang diambil

tinggal yang terakhir adalah 56 jadi disini 123456

karena ini diambil yang terkecil 5 nanti dimasukkan ke dalam listnya

nanti terkecil lagi 6 dimasukkan di listnya kebetulan ini udah urut

jadi proses ini akan selesai kalau kita sudah dapat urutan 123456

dan proses ini dilakukan kalau kebetulan dalam listnya itu udah terurut

2356 dan 14 kalau enggak nanti kita harus urutkan lagi caranya agak lebih panjang

ini algoritmanya untuk menggabungkan dua list

jadi kita punya L1 dan L2 ini udah sorted list ya jadi bukan yang sembarang

kemudian kita berikan tempat empty list disini untuk menaruh hasilnya nanti

terus kita bandingkan yang terkecil di L1 terkecil di L2 dibandingkan

kalau yang paling kecil kita masukkan ke L dan seterusnya proses dilanjutkan sampai selesai