Algoritma Merger sort menggunakan Java

Merge sort adalah algoritma yang tujuannya untuk mengurutkan data. Merge sort adalah salah satu contoh algoritma yang memanfaatkan rekursif. Gambar berikut adalah contoh ilustasi bagaimana cara kerja merge sort (gambar diambil dari wikipedia):

Pada gambar diatas, data yang diurutkan tersimpan dalam sebuah array, dengan panjang 7. Merge sort terdiri dari 2 tahap, yaitu tahapan pemecahan array, dan tahap penggabungan (merge).

Pada gambar di atas panah merah menunjukkan fase pemecahan array, dengan cara array dipecah jadi 2 bagian. jika hasil pecahannya masih besar, yaitu panjang array lebih dari 1, maka pecah lagi. Sampai pada terbentuk sekian sub-array, dengan panjang 1.

Apakah tujuannya dipecah sedemkian rupa? karena jika panjang sub-array adalah 1, maka dari sudut pandang sub-array, dia sudah pasti urut. Maka, kalau 2 sub array digabungkan (merge), dan 2 sub array ini urut, lalu dalam proses penggabungan ini juga ada pengurutan, maka hasil merge-nya juga urut. dan langkah ini berlanjut sampai semua sub-array digabungkan. inilah yang terjaid di tahap 2, yaitu panah hijau.

contohnya misalnya pada baris 3, sub-array pertama, array dengan panjang 2 yang isinya 38 dan 27, setelah dipecah, sampailah pada tahap akhir proses pemecahan karena menjadi 2 sub-array dengan panjang 1. kemudian masuk ke tahap 2, yaitu merge, dimana 38 dan 27 digabung menjadi 27 dan 38 (karena ada proses pengurutan). ini nampak pada baris ke 5 sub-array pertama. begitu seterusnya langkah ini menggabungkan sub-array secara rekursif.

secara formal merge sort didefinisikan sebagai berikut:

Merge Sort

Bagaimana menjamin bahwa algortima ini pasti mengasilkan data yang urut:

1. array dipecah secara rekursif menjadi sekumpulan sub-array yang panjangnya 1. karena itu sub-array paling akhir pasti urut.
2. peggabungan 2 sub-array disertai pengurutan.
3. hasil penggabungan sub-array secara rekursif pasti urut dikarenakan langkah nomor 2 juga pasti urut.

contoh kode menggunakan java:

public static void main(String[] args) {
		int[] a = { 6, 5, 3, 1, 8, 7, 2, 4, 0 };
		doMergerSort(a);

		for (int i = 0; i < a.length; i++)
			System.err.print(a[i] + " ");

	}

	private static void doMergerSort(int[] a) {
		mergerSort(a, 1, a.length);
	}

	private static void mergerSort(int[] a, int start, int end) {
		int n = end - start + 1;
		if (n <= 1)
			return;

		int middle = start + (n / 2) - 1;
		mergerSort(a, start, middle);
		mergerSort(a, middle + 1, end);
		merge(a, start, middle, end);
	}

	private static void merge(int[] a, int start, int middle, int end) {
		int[] b = new int[end - start + 1];

		int i = start;
		int j = middle + 1;

		for (int k = 0; k < b.length; k++) { if (j > end) {
				b[k] = a[i - 1];
				i++;
			} else if (i > middle) {
				b[k] = a[j - 1];
				j++;
			} else if (a[i - 1] < a[j - 1]) {
				b[k] = a[i - 1];
				i++;
			} else {
				b[k] = a[j - 1];
				j++;
			}
		}

		for (int k = 0; k < b.length; k++) {
			a[start - 1 + k] = b[k];
		}

	}