Merge sort berbasiskan pada paradigma “divide and conquer” . Secara sederhana algoritma penyelesaian merge sort yaitu dengan membagi suatu array menjadi dua bagian terus menerus ( rekursi ) hingga tidak dapat dibagi lagi. Kemudian antar bagian tersebut dibandingkan masing-masing elemennya untuk mengurutkan sekaligus menggabungkannya lagi.
merge sort dibagi menjadi 3 fase yaitu :
1. Divide Step
Jika array yang diberikan hanya mempunyai 1 anggota, langsung di-return bahwa sudah di sort, jika tidak, bagi array A[a . . n] menjadi 2 sub array A[a…b] dan A[b+1 .. n] masing masing mengandung setengah dari element A[a..n] yaitu b adalah tengah-tengah dari index a->n
2. Conquer Step
Conquer secara rekursif dengan men-sort dua sub array A[a..b] dan A[b+1 .. n].
3. Combine Step
Mengkombinasikan kembali elemen menjadi A[a…n] dengan menggabungkan 2 sub array yang telah di sort A[a..b] dan A[b+1 ..n] menjadi sebuah array yang telah di sort.
Analisis Merge Sort
menganalisis merge sort menggunakan master theorem yaitu menggunakan T(n) = AT(n/b) + f(n) …
basis rekursi dari fungsi merge sort ketika n = 1 dan merge sort ketika n>1 maka…
merge sort merekursif 2 array hasil pembagian array awal dan masing-masing mempuyai ukuran (n/2)
maka master theoremnya = 2T(n/2)+f(n)
dengan melihat aturan master theorem maka
T (n) = Θ(n lg n).
SOURCE CODE
berikut source code yang saya buat
#include <stdio.h>
#include <stdlib.h>
void merge(int,int,int);
void mergesort(int ,int);
int *a,*b,*c;
int main()
{
a = (int*)malloc(sizeof(int));
b= (int*)malloc(sizeof(int));
c= (int*)malloc(sizeof(int));
int n = 0;
printf(“masukkan jumlah angka = “);
scanf(“%d”,&n);
for ( int i = 0 ; i< n ;i++)
{
printf(“masukkan angka (maksimal 8 digit)”);
scanf(“%d”,&a[i]);
}
mergesort(0,n);
for ( int i = 0 ; i< n ;i++)
{
printf(“\n %d”,a[i]);
}
system(“pause”);
}
void mergesort(int lo, int hi)
{
if (lo {
int m=(lo+hi)/2;
mergesort(lo, m);
mergesort(m+1, hi);
merge(lo, m, hi);
}
}
void merge(int lo, int m, int hi)
{
int i, j, k;
// copy both halves of a to auxiliary array b
for (i=lo; i b[i]=a[i];
i=lo; j=m+1; k=lo;
// copy back next-greatest element at each time
while (i if (b[i] a[k++]=b[i++];
else
a[k++]=b[j++];
// copy back remaining elements of first half (if any)
while (i a[k++]=b[i++];
}
happy coding ^^V!
