import java.util.Arrays;

public class MergeQuickSort {

    static long perbandingan;
    static long operasi;

    public static void main(String[] args) {
        int[] asli = {5, 2, 9, 1, 7, 3, 8, 6};
        System.out.println("Data awal: " + Arrays.toString(asli));
        System.out.println();

        System.out.println("=== Merge sort (divide and conquer) ===");
        int[] a = Arrays.copyOf(asli, asli.length);
        perbandingan = 0;
        operasi = 0;
        urutMerge(a, 0, a.length - 1);
        System.out.println("Hasil          : " + Arrays.toString(a));
        System.out.println("Perbandingan   : " + perbandingan);
        System.out.println("Penyalinan     : " + operasi);
        System.out.println();

        System.out.println("=== Quick sort (partisi Lomuto) ===");
        a = Arrays.copyOf(asli, asli.length);
        perbandingan = 0;
        operasi = 0;
        urutQuick(a, 0, a.length - 1);
        System.out.println("Hasil          : " + Arrays.toString(a));
        System.out.println("Perbandingan   : " + perbandingan);
        System.out.println("Tukar posisi   : " + operasi);
    }

    // ===== Merge sort =====

    static void urutMerge(int[] a, int kiri, int kanan) {
        if (kiri >= kanan) {
            return;                      // satu elemen: sudah terurut
        }
        int tengah = (kiri + kanan) >>> 1;
        urutMerge(a, kiri, tengah);      // urut separuh kiri
        urutMerge(a, tengah + 1, kanan); // urut separuh kanan
        gabung(a, kiri, tengah, kanan);  // gabungkan dua bagian terurut
    }

    static void gabung(int[] a, int kiri, int tengah, int kanan) {
        int[] campuran = new int[kanan - kiri + 1];
        int i = kiri;
        int j = tengah + 1;
        int k = 0;

        while (i <= tengah && j <= kanan) {
            perbandingan++;
            if (a[i] <= a[j]) {          // <= menjaga stabilitas
                campuran[k++] = a[i++];
            } else {
                campuran[k++] = a[j++];
            }
            operasi++;
        }
        while (i <= tengah) {
            campuran[k++] = a[i++];
            operasi++;
        }
        while (j <= kanan) {
            campuran[k++] = a[j++];
            operasi++;
        }
        for (k = 0; k < campuran.length; k++) {
            a[kiri + k] = campuran[k];   // tulis kembali hasil gabungan
            operasi++;
        }
    }

    // ===== Quick sort (skema partisi Lomuto) =====

    static void urutQuick(int[] a, int rendah, int tinggi) {
        if (rendah >= tinggi) {
            return;
        }
        int posisiPivot = partisi(a, rendah, tinggi);
        urutQuick(a, rendah, posisiPivot - 1);   // kiri pivot: lebih kecil
        urutQuick(a, posisiPivot + 1, tinggi);   // kanan pivot: lebih besar
    }

    static int partisi(int[] a, int rendah, int tinggi) {
        int pivot = a[tinggi];           // Lomuto: elemen terakhir jadi pivot
        int batas = rendah - 1;          // batas wilayah "lebih kecil dari pivot"
        for (int j = rendah; j < tinggi; j++) {
            perbandingan++;
            if (a[j] < pivot) {
                batas++;
                tukarPosisi(a, batas, j);
            }
        }
        tukarPosisi(a, batas + 1, tinggi);   // pivot masuk posisi finalnya
        return batas + 1;
    }

    static void tukarPosisi(int[] a, int i, int j) {
        operasi++;
        int sementara = a[i];
        a[i] = a[j];
        a[j] = sementara;
    }
}