package id.ac.ut.praktikumstrukturdata.modul6;

import java.util.Arrays;

/**
 *
 * @author Nur Zain Pradana 053126827 Semester 2 Prodi Sistem Informasi UT
 * Jakarta
 *
 */
public class TugasMergeSort {

    public static void main(String args[]) {
        /**
         * Membuat Variable *
         */
        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};

        System.out.println("Array awal : ");
        printArray(arr);

        /**
         * Proses Merge Sort *
         */
        TugasMergeSort ob = new TugasMergeSort();
        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 (DESCENDING)
            ===================================
            Merge Sort adalah algoritma pengurutan dengan konsep 'divide and conquer':
            - Membagi array menjadi dua bagian secara rekursif (divide)
            - Mengurutkan tiap bagian secara terpisah
            - Menggabungkan kembali dua bagian terurut (merge)

            Pada versi descending, elemen yang lebih besar akan ditempatkan terlebih dahulu
            dengan membandingkan L[i] >= R[j].

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

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

            Contoh hasil:
            Array awal  : [25, 7, 18, 42, 13, 9, 31, 2]
            Hasil akhir : [42, 31, 25, 18, 13, 9, 7, 2]
            ===================================
            """;

        System.out.println(hasilAnalisa);
    }

    /**
     * Fungsi untuk membagi array menjadi 2 bagian secara rekursif, kemudian
     * mengurutkannya. *
     */
    void sort(int arr[], int l, int r) {

        System.out.println();
        System.out.println("Memanggil 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 dua 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 *
             */
            System.out.println("  Bagian [" + l + ".." + r + "] hanya satu elemen, tidak perlu diurutkan");
        }
    }

    /**
     * Function 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 dimasukkan 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]) { // besar dulu -> descending
                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)));
    }

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