Septian Purwandi

Metode penggabungan biasanya digunakan pada pengurutan berkas. Prinsip dari metode penggabungan sebagai berikut :

Mula-mula diberikan dua kumpulan data yang sudah dalam keadaan urut. Kedua kumpulan data tersebut harus dijadikan satu table sehingga dalam keadaan urut. Misalnya kumpulan data pertama (T1) adalah sebagai berikut :

3 11 12 23 31

Sedangkan kumpulan data kedua (T2) adalah sebagai berikut :

9 15 17 20 35

Proses penggabungan ini dapat dijelaskan sebagai berikut : mula-mula diambil data pertama dari T1 yaitu 3 dan data pertama dari T2 yaitu 9. Data ini dibandingkan, kemudian yang lebih kecil diletakkan sebagai data pertama dari hasil pengurutan, misalnya T3. Jadi T3 akan memiliki satu data yaitu 3. Data yang lebih besar yaitu 9 kemudian dibandingkan dengan data kedua dari T1, yaitu 11. Ternyata 9 lebih kecil dari 11, sehingga 9 diletakkan sebagai data kedua dari T3. Demikian seterusnya
sehingga didapat hasil sebagai berikut :

3 9 11 12 15 17 20 23 31 35

Algoritma penggabungan dapat dituliskan sebagai berikut :

1. i = 0
2. j = 0
3. J3 = 0
4. Kerjakan baris 5 sampai dengan 7 selama (i < J1) atau (j < J2)
5. J3 = J3 + 1
6. Jika (T1[i] < T2[j]) maka T3[J3] = T1[i], i = i + 1
7. Jika (T1[i] >= T2[j]) maka T3[J3] = T2[j], j = j + 1
8. Jika (i > J1) maka kerjakan baris 9, jika tidak kerjakan baris 15
9. i = j
10. Selama (i < J2) kerjakan baris 11 sampai dengan 13
11. J3 = J3 + 1
12. T3[J3] = T2[i]
13. i = i + 1
14. Selesai
15. j = i
16. Selama (j < J1) kerjakan baris 17 sampai dengan 19
17. J3 = J3 + 1
18. T3[J3] = T1[j]
19. j = j + 1



Di bawah ini merupakan prosedur penggabungan dua kumpulan data yang sudah dalam keadaan urut:

void MergeSort(int T1[],int T2[],int J1,int J2, int T3[],int *J3)
{
int i=0, j=0;
int t=0;
while ((i<J1)||(j<J2))
{
if(T1[i]<T2[j])
{
T3[t] = T1[i];
i++;
}
else
{
T3[t] = T2[j];
j++;
}t++;
}
if(i>J1)
for(i=j; i<J2; i++)
{
T3[t] = T2[i];
t++;
}
if(j>J2)
for(j=i; j<J1; j++)
{
T3[t] = T1[j];
t++;
}
*J3 = t;
}