Metode "Merge Sort" atau sering juga disebut metode penggabungan. Merge sortmerupakan algoritma pengurutan dalam ilmu komputer yang dirancang untuk memenuhi kebutuhan pengurutan atas suatu rangkaian data yang tidak memungkinkan untuk ditampung dalam memori komputer karena jumlahnya yang terlalu besar. Algoritma ini ditemukan oleh John von Neumann pada tahun 1945.
Dalam algoritma juga mengenal dua macam pengurutan, yaitu
1. urut naik (ascending) yaitu dari data yang mempunyai nilai paling kecil sampai paling besar
2. urut turun (descending) yaitu data yang mempunyai nilai paling besar sampai paling kecil.
Dimana prinsip utama yang diimplementasikan pada algoritma merge-sort seringkali disebut sebagai pecah-belah dan taklukkan (bahasa Inggris: divide and conquer). Hal ini dikarenakan algoritma sorting melakukan pembagian struktur data sebelum kemudian dioperasikan satu per satu. Intinya, algoritma ini menggunakan du aide utama, yaitu sebagai beriut:
1. Sebuah list yang kecil membutuhkan langkah yang lebih sedikit untuk pengurutan daripada sebuah list yang besar.
2. Untuk membentuk sebuah list terurut dari dua buah list terurut membutuhkan langkah yang lebih sedikit daripada membentuk sebuah list terurut dari dua buah list tak terurut.
Adapun cara kerja algoritma merge sort dengan berpola divide and conquer adalahsebagai berikut:
1. Divide : membagi list yang tak berurut menjadi dua bagian sama panjang atau boleh salah satunya lebih panjang satu elemen.
2. Conquer : membagi masing-masing dari sub-list secara rekursif sampai didapatkan list dengan ukuran 1.
3. Combine : menggabungkan 2 sub-list kembali menjadi satu list terurut.
Dengan kata lainmetode merge sort merupakan metode yang membutuhkan fungsi rekursi untuk penyelesaiannya. Proses rekursif berhenti
Jika mencapai elemen dasar. Hal ini terjadi bilamana bagian yang akan diurutkan menyisakan tepatsatu elemen. Sisa pengurutan satu elemen tersebut menandakan bahwa bagian tersebut telahterurut sesuai rangkaian.
Untuk lebih jelasnya, perhatikan gambar berikut :
Berikut ini implementasi sederhana dari Algoritma Merge Sort dengan C++ dan Tool yang digunakan Code Block 8.02
#include <iostream>using namespace std;
void merge(int low, int mid, int up);
void mergeSort(int low, int up);
int a[50];
int main()
{
int jumlahBil,i;
cout<<"Masukkan Jumlah element Array"<< endl;
cin>>jumlahBil;
for(int i=0; i<jumlahBil;i++)
{
cout<<"Bilangan ke-"<< i+1 << endl;
cin>>a[i];
}
mergeSort(1,jumlahBil);
for(i=1;i<=jumlahBil;i++)
cout<<a[i]<<" ";
cout<<endl;
return 0;
}
void merge(int low, int mid, int up)
{
int h, i,j,k;
int b[50];
h = low;
i = low;
j = mid+1;
while((h<=mid)&&(j<=up))
{
if(a[h] < a[j])
{
b[i]=a[h];
h++;
}
else
{
b[i]=a[j];
j++;
}
i++;
}
if(h>mid)
{
for(k=j;k<=up;k++){
b[i]=a[k];
i++;
}
}
else
{
for(k=h;k<=mid;k++)
{
b[i]=a[k];
i++;
}
}
for(k=low;k<=up;k++) a[k]=b[k];
}
void mergeSort(int low, int up)
{
int mid;
if(low<up)
{
mid=(low+up)/2;
mergeSort(low,mid);
mergeSort(mid+1,up);
merge(low,mid,up);
}
}
sumber : usahawan-maju.blogspot.co.id and 7seasons.wordpress.com
