Merge Sort

Merge sort merupakan salah satu algoritma yang digunakan untuk memecahkan masalah pengurutan/sorting. Merge sort menggunakan teknik tingkat lanjut dalam melakukan sorting yakni teknik membagi suatu deret elemen yang akan dilakukan sorting kemudian masing-masing bagian dilakukan sorting secara terpisah dalam mekanisme rekursif. Setelah tiap-tiap bagian dilakukan sorting maka akan dilakukan penyatuan kembali/merge sehingga menghasilkan suatu deret elemen yang terurut. Teknik sorting yang diterapkan oleh algoritma merge sort biasa disebut divide and conquer.

Dalam implementasinya, algoritma merge sort memerlukan tiga array yang digunakan sebagai penampungan elemen array sementara. Dua array digunakan untuk menampung elemen array yag dibagi dan satu array lagi digunakan sebagai wadah tempat array output yag telah terurut. Dengan menggunakan array lebih dari satu membuat algoritma ini memerlukan banyak resource system. Akan tetapi hal ini dapat diminimalisir dengan menggunakan dua array.

Sebelum mendalami algoritma merge sort, mari kita mengetahui garis besar dari konsep divide and conquer karena merge sort mengadaptasi pola tersebut.

Pola Divide and Conquer

Beberapa algoritma mengimplementasikan konsep rekursi untuk menyelesaikan permasalahan. Permasalahan utama kemudian dipecah menjadi sub-masalah, kemudian solusi dari sub-masalah akan membimbing menuju solusi permasalahan utama.

Algoritma untuk merge sort ialah sebagai berikut :

   1.      Untuk kasus n=1, maka table a sudah terurut sendirinya (langkah solve)

   2.      Untuk kasus n>1, maka :

    a       DIVIDE: bagi table a menjadi dua bagian, bagian kiri dan bagian kanan, masing-masing bagian
                         berukuran n/2 elemen.

    b       CONQUER: secara rekursif, terapkan algoritma D-and-C pada masing masing bagian.

    c      MERGE: gabung hasil pengurutan kedua bagian sehingga diperoleh table a yang terurut.

    

    Ilustrasi

   

   Konsep dari ilustrasi merge sort di atas adalah sebagai berikut :

·        1.  Bagi list besar menjadi setengahnya

·        2. Lakukan hal ini secara rekursif sampai diperoleh list dengan satu elemen saja

·        3. List tersebut digabung lagi menjadi sebuah list besar yang sudah terurut.

    Algoritma Merge Sort

procedure mergesort(input/output a : tabelint, input i, j : integer)

{ mengurutkan tabel a[i..j] dengan algoritma merge sort

masukan: tabel a dengan n elemen

keluaran: tabel a yang terurut }

deklarasi:

k : integer

algoritma:

if i < j then { ukuran(a)> 1}

k←(i+j) div 2

mergesort(a, i, k)

mergesort(a, k+1, j)

merge(a, i, k, j)

endif   

endprocedure

procedure merge(input/outputa : tabelint, input kiri,tengah,kanan : integer)

{ menggabung tabel a[kiri..tengah] dan tabel a[tengah+1..kanan] menjadi tabel

a[kiri..kanan] yang terurut menaik.

masukan: a[kiri..tengah] dan tabel a[tengah+1..kanan] yang sudah terurut

menaik.

keluaran: a[kiri..kanan] yang terurut menaik. }

deklarasi :

b : tabelint

i, kidal1, kidal2 : integer

algoritma:

kidal1←kiri { a[kiri .. tengah] }

kidal2←tengah + 1 { a[tengah+1 .. kanan] }

i←kiri

while (kidal1 ≤ tengah) and (kidal2 ≤ kanan) do

if akidal1 ≤ akidal2 then

bi←akidal1

kidal1←kidal1 + 1

      else

bi←akidal2

kidal2←kidal2 + 1

endif

i←i + 1

endwhile

{ kidal1 > tengah or kidal2 > kanan }

{ salin sisa a bagian kiri ke b, jika ada }

while (kidal1 ≤ tengah) do

bi←akidal1

kidal1←kidal1 + 1

i←i + 1

endwhile

{ kidal1 > tengah }

{ salin sisa a bagian kanan ke b, jika ada }

while (kidal2 ≤ kanan) do

bi←akidal2

kidal2←kidal2 + 1

i←i + 1

endwhile

{ kidal2 > kanan }

{ salin kembali elemen-elemen tabel b ke a }

for i←kiri to kanan do

ai←bi

endfor

{ diperoleh tabel a yang terurut membesar }

endprocedure

Semoga bermanfaat