MergeSort Algorithm

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 + " ");
        }
    }
}