METODA MERGE SORT (TWO-WAY MERGE SORT)

Metoda merge sort juga disebut two way merge sort. Langkah-langkah pengurutan dengan merge sort secara garis besar dapat dijelaskan sebagai berikut.

Andaikan terdapat sebuah vektor K dengan cacah elemen data sebanyak N dalam kondisi tidak terurut. Untuk mengurutkan semua data-data dalam K, mula-mula setiap elemen dalam vektor K dianggap sebagai sebuah vektor yang masing-masing mempunyai sebuah elemen data. Dengan demikian akan terdapat N vektor dengan cacah elemen masing-masing adalah 1 buah. Selanjutnya setiap pasang vektor yang beruntun kita gabungkan menjadi sebuah vektor baru. Jika kita menginginkan hasil secara urut naik, maka pada saat menggabungkan kedua vektor tersebut sekaligus dilakukan perbandingan dan pertuaran posisi antar elemen data sedemikian rupa sehingga data yang lebih kecil akan akan ditempatkan pada posisi yang mendahului data lain yang lebih besar. Pada akhir langkah pertama ini, kita akan memiliki vektor baru sebanyak N/2 yang masing-masing dalam kondisi urut naik. Cacah elemen pada masing-masing vektor adalah 2 buah, kecuali jika N bernilai ganjil maka akan terdapat N/2+1 vektor baru dimana salah satu vektor hanya memiliki sbuah elemen data.

Pada langkah selanjutnya, setiap pasang vektor yang beruntun  dilakukan penggabungan dan sekaligus dapat pertukaran posisi antar data sehingga akan terbentuk vektor-vektor baru. Demikian proses penggabungan dan pertukaran posisi data secara terus menerus akan dilakukan sehingga pada akhirnya akan diperoleh sebuah vektor baru yang memuat semua elemen data dalam vektor sumber dalam kondisi urut naik.

Sebagai ilustrasi untuk memperjelas proses pengurutan dalam metoda merge sort, maka berikut ini akan diberikan contoh penenrapannya. Diketahui sebuah vektor yang akan diurutkan secara urut naik, yaitu K yang memiliki delapan elemen data sebagai berikut.

Contoh :

87    74    71    100    75    25    56    90

Ilustrasi proses pengurutan vektor K dengan metode merge sort secara ringkas adalah ditunjukan oleh gambar dibawah ini.

Contoh ilustrasi pengurutan data dengan metoda merge sort.

Dalam contoh diatas, mula-mula vektor K akan dipecah menjadi vektor-vektor  baru yang masing-masing memiliki satu elemen data sehingga akan terdapat delapan vektor.

1. Pada langkah pertama, setiap pasang vektor yang berurutan akan digabungkan dan sekaligus dibandingkan untuk menempatkan data yang lebih kecil pada lokasi yang lebih awal. Dalam contoh diatas 87 akan digabungkan dengan 74, 71 dengan 100, 75 dengan 25, dan 56 dengan 90.

2. Pada langkah kedua akan menghasilkan empat vektor baru yang masing-masing telah diurut.

3. Pada Langkah ketiga akan menggabungkan kembali sekaligus mengatur lokasi setiap data yang digabungkan tersebut sehingga akhirnya akan menghasilkan 2 vektor baru.

4. Pada langkah terakhir, yaitu langkah keempat maka dua vektor hasil peggabungan pada langkah ketiga akan digabungkan dan diatur kembali.

Dari ilustrasi diatas terlihat bahwa untuk mengurutkan vektor KK yang memiliki  delapan elemen data akan memerlukan 3 langkah penggabungan dimana masing-masing langkah terdiri dari beberapa proses perbandingan dan pertukaran lokasi elemen data. Selanjutnya, untuk menuliskan solusi bentuk algoritma prosedur pengurutan data secara urut naik dengan metoda merge sort akan digunakan beberapa variable I,J,Kdan L adalah sebagai pencacah pada proses perulangan. Variabel N adalah menunjukan cacah elemen vektor sumber KK. Variable ITERASI menyatakan banyaknya langkah yang harus dilakukan untuk mengurutkan data. SUB  ITERASI adalah variable untuk menentukan banyaknya SUB Iterasi pada setiap Iterasi. Variabel UKURAN menunjukan cacah elemen vektor pada iterasi yang bersesuaian.sedangkan R,S,dan T adalah variabel-variabel yang akan digunakan sebagai pencacah. Untuk memperoleh vektor yang urut maka cacah Iterasi yang harus dilakukan adalah sebanyak M dimana sama dengan log₂N. Algoritma prosedur pengurutan data dengan metode merge sort dapat dituliskan sebagai berikut ini :

Masukan vektor K yang memuat N buah data yang akan diurutkan KK adalah vektor hasil dalam kondisi urut naik.

1. Mulai

2. Proses berulang langkah-3 sampai dengan langkah-8

FOR ITERASI=1 TO M

3.Inisialisasikan  untuk iterasi

UKURAN =2…(ITERASI-1)

P=1

Q=P+UKURAN

SUB ITERASI=N/(2xITERASI)

4. Proses berulang langkah-5 s/d langkah-8 untuk setiap iterasi

FOR S=1 TO SUB ITERASI

5. Inisialisasi prosedur simple merge

I=P

J=Q

T=P

6. Proses memang berulang untuk membandingkan antar data dan menemukan  elemen

   terkecil

WHILE((1+1-P<=UKURAN)AND(J+1-Q<=UKURAN))

IF ITERASI=”GANJIL”

Jika ya,IF K[I]<=K[J]

Jika ya,tentukan KK[T]=K[I]

I=I+1

T=T+1

Jika tidak,tentukan KK[T]=K[J]

J=J+1

T=T+1

Jika tidak,IF KK[I]<=KK[J]

Jika ya,tentukan K[T]=KK[I]

I=I+1

T=T+1

Jika tidak,tentukan K[T]=KK[J]

J=J+1

T=T+1

7. Copykan sisa elemen data yang tidak terproses dari vektor sumber ke vektor

hasil

IF I+1-P>UKURAN

Jika ya,IF ITERASI=”GANJIL”

Jika ya,lakukan proses berulang

FOR R=J TO Q+UKURAN -1

KK[T]=K[R]

T=T+1

Jika tidak,IF ITERASI=”GANJIL”

Jika ya,lakukan proses berulang

FOR R=1 TO P +UKURAN -1

KK[I]=K[R]

T=T+1

JIka tidak,lakukan proses berulang

FOR R=1 TO P+UKURAN -1

K[T]=KK[R]

T=T+1

8. Perbaharui indikasi vektor

P=Q+UKURAN

Q=P+UKURAN

9. Copykan ulang jika diperlukan

IF M=”GANJIL”

Jika ya, lakukan proses berulang

FOR I=1 TO N

K[I]=KK[I]

10. Cetak hasil

11. Selesai

Contoh lain dari merge sort (two way merging) secara mendasar.

1. Bagi urutan urutan menjadi dua bagian dengan panjang n/2 dan n/2.

2. Mengurutkan berulang pada setiap 2 urutan, dan

3. Gabungkan urutan yang diurut hingga mencapai hasil akhir

Pengurutan dengan merge sort adalah perulangan, pambagian dan penggabungan. Dasarnya, kita mempunyai urutan dengan satu elemen pasti didalamnya. Ketika urutan sudah diurutkan, tidak perlu diurutkan lagi. Pengurutannya yaitu dengan n>1 elemen .