Penjelasan Simple Merge Sort

gistfile1.txt

Merge Sort

Merge sort sebenarnya ya sorting mengurutkan dari kecil ke besar dari besar ke kecil, implementasinya yg disorting itu bisa angka (int, float atau double), bisa juga karakter ASCII atau Unicode.
Bedanya sorting di sini menggunakan prinsip divide and conquer atau devide et impera :D

Untuk memahami merge sort, perlu pemahaman tentang fungsi rekursif, kalo belom tahu ya belajar dulu tentang rekursif.

Ada tiga step penting di merge sort, yaitu:

1. Sort setengah bagian kiri dari array. (rekursif)
2. Sort setengah bagian kanan dari array. (rekursif)
3. Gabungin bagian yg sebelah kiri dan bagian yg sebelah kanan menjadi bagian yg tersort. 

Ini bagian rekursifnya:

void mergesort(int array[], int indexAwalArray, int indexAkhirArray)
{
  if( indexAwalArray < indexAkhirArray)
	{
		int indexTitikTengahArray = (indexAwalArray + indexAkhirArray ) / 2;
		mergesort(array, indexAwalArray, indexAkhirArray); // sorting bagian sebelah kiri
		mergesort(array, indexTitikTengahArray+1, indexAkhirArray); // sorting bagian sebelah kanan
		merge(array, indexAwalArray, indexTitikTengahArray, indexAkhirArray); // merge keduanya
	}
}

Hint: Usahain nama variabel yg mudah dimengerti orang.

Example :

array : [ 2, 3, 12, 70, 8]

titik tengah : 12 

array kiri : [2, 3] // sudah tersort

array kanan : [8, 70]

Lalu selanjutnya akan dilakukan proses merging, gabungin yg sebelah kiri dan sebelah kanan.

void merge(int array[],int indexAwalArray,int indexTitikTengahArray,int indexAkhirArray)
{
	int helper[n]; // helper berfngsi sebagai temporary directory

	// di sini isi array akan dicopy ke helper array
	for (int i = indexAwalArray; i <= indexAkhirArray; i++) {
      helper[i] = array[i];
    }

    // nah, variabel di sini buat ngebantu kita bandingin yg bagian kiri dan kanan array
    // yg di-split tadi

	int i = indexAwalArray; 
	int j = indexTitikTengahArray + 1;
	int k = indexAwalArray;

	/*
		jadi prosesnya ngurutin nih, dari index pertama sampai titikTengah
		ambil nilai arraynya mulai dr index ke i ampe ke indexTitikTengahArray kemudian bandingin hasilnya dengan nilai pada indexTitikTengahArray + 1 hingga ke indexAkhirArray

		Krn defaultnya ascending, maka kalau sebelah kiri lebih kecil ya berarti yg lebih dulu masuk. Kalau lebih besar, nilai array bagian kanan yg masuk ke array akhir, kemudian index naik. 
		Kemudian lanjut ke index berikutnya sampai nyampe titik tengah.

		Kalau descending gmn kakak? :D :D :D 
	*/

	while(i <= indexTitikTengahArray && j <= indexAkhirArray) {
		if (helper[i] <= helper[j]) {
			array[k] = helper[i];
			i++;
		} else {
			array[k] = helper[j];
			j++;
		}
		k++;
	}

	// bagian ini akan memasukkan sisa nilai yg ada di array sebelah kiri ke array yg
	// akan di return.
	while(i <= indexTitikTengahArray){
		array[k] = helper[i];
		k++;
		i++;
	}
}

Fungsi merge akan melakukan ini:
1. 2 dan 8 >> [2]
2. 3 dan 8 >> [2, 3]
3. 12 dan 8 >> [2, 3, 8]
4. 12 dan 70 >> [2, 3, 8, 12]

Sisanya 70 yg sendirian akan ditambahkan ke array: [2, 3, 8, 12, 70]

Sebagai tambahan Merge Sort ini complexitynya O(n log n).
Untuk penjelasan detil mengenai complexity, bisa baca buku Intro to Algorithm atau tanya ke Pak Adilla di forum ini juga.

Thanks,
Kalau ada yg mau ditambahkan silahkan, atau menyanggah, silakan.


Reference (maaf pakai contohnya Java, soalnya algorithma pada contoh ini lebih simple): 

- http://www.vogella.com/articles/JavaAlgorithmsMergesort/article.html