Algoritma Merge Sort

Secara literal merge sort berarti mengurutkan dengan cara menggabungkan. Sesuai dengan namanya, algoritma pengurutan merge sort melibatkan penggabungan secara berulang-ulang hingga membentuk rangkaian nilai yang terurut.

Berdasarkan jenisnya, algoritma ini termasuk dalam kategori algoritma divide and conquer, yang bekerja secara rekursif (lihat artikel) memecah kemudian menggabungkan rangkaian nilai yang ingin diurutkan sampai seluruh nilai menjadi terurut.

Penjelasan mekanisme pengurutan

Algoritma merge sort sendiri sebenarnya tidak hanya menggabungkan. Algoritma ini terlebih dahulu melakukan pemecahan berulang-ulang, baru kemudian diikuti dengan penggabungan yang disertai pengurutan.

Berikut adalah animasi yang memperlihatkan dua tahapan tersebut dengan sangat jelas (sumber: wikimedia common), kemudian diikuti dengan penjelasan dan contoh kode untuk implementasinya.

Tahap pemecahan

Tahap pemecahan merupakan tahap divide, menyederhanakan persoalan ke dalam bentuk yang lebih kecil. Pada tahap ini, algoritma merge sort melakukan pemecahan rangkaian nilai (list) menjadi dua bagian (dipecah di tengah) terus menerus hingga hanya tersisa satu elemen pada tiap pecahan. Lihat potongan kode di bawah untuk implementasinya.

  jumlah_bilangan =  len(list_bilangan)
  if jumlah_bilangan > 1:
    posisi_tengah = len(list_bilangan)//2
    potongan_kiri = list_bilangan[:posisi_tengah]
    potongan_kanan = list_bilangan[posisi_tengah:]
    merge_sort(potongan_kiri)
    merge_sort(potongan_kanan)

Potongan kode di atas menunjukkan bahwa rangkaian bilangan (pada variabel list_bilangan), dipecah terus menerus menjadi potongan yang lebih kecil secara rekursif hingga akhirnya hanya berisi satu elemen saja.

Tahap penggabungan

Tahap penggabungan adalah tahap conquer, kebalikan dari proses pemecahan, dimana seluruh potongan yang dihasilkan dari proses pemecahan kemudian digabungkan secara bertingkat.

Pada tahap inilah juga terjadi pengurutan, karena saat digabungkan, masing-masing elemen dari dua potongan yang akan digabung, dibandingkan terlebih dahulu untuk kemudian diletakkan pada sebuah potongan baru sesuai urutan nilainya. Ini berarti bahwa pada masing-masing pecahan yang akan digabungkan, seluruh elemennya sudah terurut dari proses penggabungan sebelumnya.

Perhatikan potongan kode ini untuk lebih jelasnya

    jumlah_bilangan_kiri = len(potongan_kiri)
    jumlah_bilangan_kanan = len(potongan_kanan)
    c_all,c_kiri,c_kanan = 0,0,0 # pencacah/counter
    # selama masih ada elemen pada potongan
    while c_kiri < jumlah_bilangan_kiri or c_kanan < jumlah_bilangan_kanan:
      # elemen di potongan kiri habis
      if c_kiri == jumlah_bilangan_kiri: 
        list_bilangan[c_all] = potongan_kanan[c_kanan]
        c_kanan = c_kanan + 1
      # elemen di potongan kanan habis
      elif c_kanan == jumlah_bilangan_kanan: 
        list_bilangan[c_all] = potongan_kiri[c_kiri]
        c_kiri = c_kiri + 1
      # nilai antrian elemen di potongan kiri lebih kecil
      elif potongan_kiri[c_kiri] <= potongan_kanan[c_kanan]: 
        list_bilangan[c_all] = potongan_kiri[c_kiri]
        c_kiri = c_kiri + 1
      # nilai antrian elemen di potongan kanan lebih kecil
      else: 
        list_bilangan[c_all] = potongan_kanan[c_kanan]
        c_kanan = c_kanan + 1
      c_all = c_all + 1

Kode lengkap

Berikut adalah source code lengkap algoritma merge sort dalam bahasa pemrograman python.

Semoga bermanfaat,

Salam

Series Navigation

<< Algoritma Insertion SortAlgoritma Quick Sort >>