Tugas2MergeSort.java

import java.util.Arrays;

public class Tugas2MergeSort {
    /** Membuat Function Sort
     *  Berfungsi untuk membagi array menjadi 2 bagian secara rekursif,
     *  Kemudian mengurutkannya secara Descending dari Terbesar
     *  Sampai Terkecil
     **/

    void sort(int arr[], int l, int r){

        System.out.println();
        System.out.println("Memanggil Function Sort(arr, " + l + ", " + r + ") : bagian saat ini " + Arrays.toString(Arrays.copyOfRange(arr, l, r + 1)));

        if(l < r)
        {
            int m = (l + r) / 2;
            System.out.println("  Membagi Menjadi 2 Bagian : [" + l + ".." + m + "] dan [" + (m+1) + ".." + r + "]");

            /** Urutkan Bagian Kiri **/
            sort(arr, l, m);

            /** Urutkan Bagian Kanan **/
            sort(arr, m + 1, r);

            /** Gabungkan 2 Bagian yang sudah terurut secara Descending **/
            merge(arr, l, m, r);

        } else {
            /** Tidak perlu diurutkan, karena hanya ada 1 elemen saja **/
            System.out.println("  Bagian["+l+".."+ r +"] hanya satu elemen, tidak perlu diurutkan");
        }

    }



    /** Membuat Function Merge
     * Untuk menggabungkan 2 bagian array yang sudah terurut
     */

    void merge(int[] arr, int l, int m, int r)
    {
        int n1 = m - l + 1;
        int n2 = r - m;

        int L[] = new int[n1];
        int R[] = new int[n2];

        /** Menyalin elemen ke array sementara L & R **/
        for(int i = 0; i < n1; i++)
        {
            L[i] = arr[l + i];
        }

        for(int j = 0; j < n2; j++){
            R[j] = arr[m + 1 + j];
        }

        System.out.println();
        System.out.println("Memulai proses Merge untuk indeks ["+l+".."+m+"] dan ["+(m+1)+".."+r+"]");
        System.out.println("  Bagian Kiri (L) : " + Arrays.toString(L));
        System.out.println("  Bagian Kanan (R) : " + Arrays.toString(R));

        int i = 0, j = 0;
        int k = l;

        /** Membandingkan elemen dari L dan R lalu dimasukan kedalam array utama arr **/
        while (i < n1 && j < n2)
        {
            System.out.println("  Bandingkan L["+i+"] = " + L[i] + " dengan R["+j+"] = " + R[j]);

            if(L[i] >= R[j])
            {
                arr[k] = L[i];
                System.out.println("    Ambil L["+i+"] = " + L[i] + " ke arr["+k+"]");
                i++;
            } else {
                arr[k] = R[j];
                System.out.println("    Ambil R["+j+"] = " + R[j] + " ke arr["+k+"]");
                j++;
            }
            k++;
            System.out.println("      Hasil sementara : " + Arrays.toString(arr));
        }

        /** Jika masih ada sisa elemen di L, masukkan ke array utama arr. **/
        while(i < n1)
        {
            arr[k] = L[i];
            i++;
            k++;
        }
        /** Jika masih ada sisa elemen di R, masukkan ke array utama arr. **/
        while(j < n2)
        {
            arr[k] = R[j];
            j++;
            k++;
        }

        System.out.println("  Selesai merge untuk indeks ["+l+".."+r+"]: " + Arrays.toString(Arrays.copyOfRange(arr, l, r + 1)));

    }


    /** Membuat Function untuk mencetak isi array, selain menggunakan Library Arrays.**/
    static void printArray(int arr[])
    {
        int n = arr.length;
        for(int i = 0; i < n; i++)
        {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }


    /** Membuat Function Main **/
    public static void main(String args[]) {
        /** Membuat Variabel yang akan diurutkan menggunakan merge sort **/
        int a1 = 25;
        int a2 = 7;
        int a3 = 18;
        int a4 = 42;
        int a5 = 13;
        int a6 = 9;
        int a7 = 31;
        int a8 = 2;

        int arr[] = {a1, a2, a3, a4, a5, a6, a7, a8};

        /** menampilkan array awal **/
        System.out.println("Array awal : ");
        printArray(arr);

        /** Process Merge Sort **/
        Tugas2MergeSort ob = new Tugas2MergeSort();
        ob.sort(arr, 0, arr.length - 1);

        System.out.println();
        System.out.println("Hasil array menggunakan Merge Sort secara Descending : ");
        printArray(arr);

        /** Analisa Algoritma Merge Sort **/
        String hasilAnalisa = """
                              ==================================================
                              KESIMPULAN ALGORITMA MERGE SORT
                              ==================================================

                              Merge Sort adalah algoritma pengurutan dengan konsep
                              'divide dan conquer', dimana :
                              - Membagi array menjadi dua bagian secara rekursif (divide)
                              - Mengurutkan kembali tiap bagian yang terpisah
                              - Menggabungkan kembali 2 bagian secara terurut.

                              Kelebihan :
                              - Stabil dan efisien untuk data besar
                              - Waktu eksekusi konsisten di semua kasus

                              Kekurangan :
                              - Membutuhkan memori tambahan (untuk array sementara)
                              - Kurang efisien untuk data kecil

                              Dari Source Code ini, Contoh Hasilnya :
                              Array Awal : [25, 7, 18, 42, 13, 9, 31, 2]
                              Hasil Akhirnya : [42, 31, 25, 18, 13, 9, 7, 2]
                              """;

        System.out.println(hasilAnalisa);

    }

}