class MergeSort {
/**
* tahap 1: buat sebuah fungsi yg digunakan untuk mengurutkan data dengan tiga buah parameter yaitu
* arr[]: data yang akan diurutkan,
* left: index awal dari data yang akan diurutkan,
* right: index akhir dari data yang akan diurutkan.
*/
public void mergeSort(int[] arr, int left, int right) {
/**
* tahap 2: kalau index data kiri >= index data kanan, artinya data yang diproses
* hanya memiliki 1 elemen atau sudah tidak ada elemen lagi yang akan dibandingkan
* sehingga kita bisa langsung berhenti/mereturn proses yg sedang berjalan
* karena jika hanya satu elemen maka sudah pasti datanya dalam keadaan terurut.
*/
if (left >= right) {
return;
}
/**
* kalau kondisi data kiri >= data kanan belum terpenuhi artinya data tersebut masih ada lebih dari satu elemen
* oleh karena itu kita harus membagi data tersebut menjadi dua bagian yg lebih kecil, sehingga tersisa satu elemen
* dengan demikian kita dapat tentukan titik tengah dari data kiri dan kanan itu terlebih dahulu.
*/
int mid = (left + right) / 2;
/**
* setelah mengetahui titik tengah
* kita divide/bagi menjadi 2 bagian lagi dengan menggunakan recursive untuk mengulangi proses yg sama yaitu
* bagian kiri: dari index kiri sampai titik tengah
* bagian kanan: dari titik tengah + 1 sampai index kanan.
* untuk catatan: recursive membentuk call stack dengan prinsip sama seperti mekanisme LIFO
*/
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
/**
* Tahap 3: setelah data tersebut berhasil diurutkan
* gabungkan kembali dua bagian kecil menjadi satu bagian besar yg sudah terurut
* untuk mencapai itu kita buat fungsi baru untuk melakukan merge().
*/
merge(arr, left, mid, right);
}
/**
* buat sebuah fungsi yg digunakan untuk menggabungkan dua bagian kecil menjadi satu bagian besar
* fungsi merge ini akan memiliki 4 parameter yaitu
* arr[]: data utama yang akan diurutkan,
* left: index awal dari data bagian kiri,
* mid: nilai tengah untuk mengetahui batas tengah bagian kiri dan kanan,
* right: index akhir dari data bagian kanan,
*/
public void merge(int[] arr, int left, int mid, int right) {
/**
* cari tahu berapa panjang tiap bagian.
* node1 = mid - left + 1
* node2 = right - mid
* siapkan dua array sementara (temp) untuk menampung data bagian kiri dan kanan
* leftArr: new int[node1]
* rightArr: new int[node2]
*/
int node1 = mid - left + 1;
int node2 = right - mid;
int[] leftArr = new int[node1];
int[] rightArr = new int[node2];
/**
* salin data terlebih dahulu dari kedua array agar lebih mudah dibandingkan
*/
for (int i = 0; i < node1; i++) {
leftArr[i] = arr[left + i];
}
for (int j = 0; j < node2; j++) {
rightArr[j] = arr[mid + 1 + j];
}
/**
* selanjutnya buat pointer, satu untuk array kiri, satu untuk array kanan
* dan satu lagi penanda posisi untuk menulis hasil ke array utama
* pointer kiri = i
* pointer kanan = j
* pointer utama = k
*/
int i = 0;
int j = 0;
int k = left;
/**
* lakukan perulangan terus sampai salah satu array bagian kiri dan kanan habis (tidak ada elemen lagi)
* lalu didalam proses kita bandingkan elemen dari kedua array temp
* jika elemen kiri lebih besar dari elemen kanan
* maka elemen kiri dimasukan dulu ke posisi k di array utama
* kemudian i (pointer kiri) di geser ke kanan dengan melakukan increement
* sebaliknya, jika elemen kanan lebih besar dari elemen kiri
* maka elemen kanan dimasukan dulu ke posisi k di array utama
* dan j (pointer kanan) di geser dengan melakukan increment
*/
while (i < node1 && j < node2) {
if (leftArr[i] <= rightArr[j]) {
arr[k] = leftArr[i];
i++;
} else {
arr[k] = rightArr[j];
j++;
}
k++;
}
/**
* setelah salah satu habis, mungkin masih ada sisa elemen di sisi lain (kiri atau kanan)
* kita cukup salin sisa elemen itu ke posisi k di array utama
* karena sisa elemen itu sudah pasti terurut dengan benar
*/
while (i < node1) {
arr[k] = leftArr[i];
i++;
k++;
}
while (j < node2) {
arr[k] = rightArr[j];
j++;
k++;
}
}
}
public class Main{
public static void main(String[] args) {
int[] arr = {10, 1, 5, 8, 2, 7, 3, 6, 4};
MergeSort mergeSort = new MergeSort();
mergeSort.mergeSort(arr, 0, arr.length - 1);
for (int i : arr) {
System.out.print(i + " ");
}
}
}
