// 13. hét – Összefésülő rendezés (merge sort)
// Futtatás: java MergeSort.java
import java.util.Arrays;

public class MergeSort {

    // Rendezi az a[lo..hi] részt (zárt intervallum)
    //   Eljárás ÖsszefésülőRendezés(A, bal, jobb)
    //     Ha bal < jobb akkor
    //       közép ← (bal + jobb) div 2
    //       ÖsszefésülőRendezés(A, bal, közép)
    //       ÖsszefésülőRendezés(A, közép + 1, jobb)
    //       Összefésül(A, bal, közép, jobb)
    //   Eljárás vége
    static void mergeSort(int[] a, int lo, int hi, int depth, boolean trace) {
        if (lo >= hi) return; // 0 vagy 1 elem: már rendezett (alapeset)
        int mid = lo + (hi - lo) / 2;
        mergeSort(a, lo, mid, depth + 1, trace);
        mergeSort(a, mid + 1, hi, depth + 1, trace);
        merge(a, lo, mid, hi);
        if (trace) System.out.println("  ".repeat(depth) + "összefésülve [" + lo + ".." + hi + "]: "
                + Arrays.toString(Arrays.copyOfRange(a, lo, hi + 1)));
    }

    // Két szomszédos rendezett rész (a[lo..mid] és a[mid+1..hi]) összefésülése – O(n), O(n) segédtár
    static void merge(int[] a, int lo, int mid, int hi) {
        int[] left = Arrays.copyOfRange(a, lo, mid + 1);
        int[] right = Arrays.copyOfRange(a, mid + 1, hi + 1);
        int i = 0, j = 0, k = lo;
        while (i < left.length && j < right.length) {
            if (left[i] <= right[j]) a[k++] = left[i++]; // <= : egyenlőnél a bal oldali jön előbb → STABIL
            else a[k++] = right[j++];
        }
        while (i < left.length) a[k++] = left[i++];
        while (j < right.length) a[k++] = right[j++];
    }

    public static void main(String[] args) {
        int[] a = { 38, 27, 43, 3, 9, 82, 10, 1 };
        System.out.println("kezdet: " + Arrays.toString(a));
        mergeSort(a, 0, a.length - 1, 0, true);
        System.out.println("eredmény: " + Arrays.toString(a));
    }
}