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);

    }
    
}