Taller Merge - emilioone05/Analisis_Algoritmos_utpl GitHub Wiki

public class MergeAlgorithm {

    public static void merge(int[] A, int p, int q, int r) {
        // Tamaños de los subarreglos izquierdo y derecho
        int nL = q - p + 1; // Longitud de A[p:q]
        int nR = r - q;      // Longitud de A[q+1:r]

        // Crear arreglos temporales L y R
        int[] L = new int[nL];
        int[] R = new int[nR];

        // Copiar datos a L[] y R[]
        for (int i = 0; i < nL; i++) {
            L[i] = A[p + i];
        }
        for (int j = 0; j < nR; j++) {
            R[j] = A[q + 1 + j];
        }

        // Índices para recorrer L, R y el arreglo principal A
        int i = 0, j = 0, k = p;

        // Fusionar L y R en A[p:r]
        while (i < nL && j < nR) {
            if (L[i] <= R[j]) {
                A[k] = L[i];
                i++;
            } else {
                A[k] = R[j];
                j++;
            }
            k++;
        }

        // Copiar elementos restantes de L[] (si los hay)
        while (i < nL) {
            A[k] = L[i];
            i++;
            k++;
        }

        // Copiar elementos restantes de R[] (si los hay)
        while (j < nR) {
            A[k] = R[j];
            j++;
            k++;
        }
    }

    public static void main(String[] args) {
        // Ejemplo de uso
        int[] arr = {12, 11, 13, 5, 6, 7};
        int p = 0;                  // Índice inicial
        int r = arr.length - 1;     // Índice final
        int q = (p + r) / 2;        // Punto medio

        System.out.println("Arreglo original:");
        for (int num : arr) {
            System.out.print(num + " ");
        }

        // Llamar a merge
        merge(arr, p, q, r);

        System.out.println("\nArreglo después de MERGE:");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}