Implementación de MERGE en código - andres726127/An-lisis-de-Algoritmos GitHub Wiki

 package algoritmob1;

 import java.util.List;
 public class AlgoritmoB1 {

    public static void merge(int[] A, int p, int q, int r) {

        int nL = q - p + 1; // length of A[p : q]
        int nR = r - q;     // length of A[q + 1 : r]

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

        // Copiar elementos a L
        for (int i = 0; i < nL; i++) {
            L[i] = A[p + i];
        }

        // Copiar elementos a R
        for (int j = 0; j < nR; j++) {
            R[j] = A[q + 1 + j];
        }

        int i = 0, j = 0;
        int k = p;

        // Mezclar 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 lo que queda de L, si hay
        while (i < nL) {
            A[k] = L[i];
            i++;
            k++;
        }

        // Copiar lo que queda de R, si hay
        while (j < nR) {
            A[k] = R[j];
            j++;
            k++;
        }
    }

    // Método auxiliar para probar
    public static void main(String[] args) {
        int[] A = {2, 4, 6, 8, 1, 3, 5, 7}; // ya están ordenadas dos mitades
        int p = 0;
        int q = 3;
        int r = 7;

        merge(A, p, q, r);

        // Imprimir arreglo resultante
        for (int num : A) {
            System.out.print(num + " ");
        }
    }
 }

Desarrollé el método merge en Java siguiendo paso a paso el pseudocódigo mostrado en la imagen. Este método toma un arreglo parcialmente ordenado (dos mitades) y las fusiona en un solo segmento ordenado. Utiliza arreglos temporales para copiar los valores, compara elementos y los vuelve a colocar en orden en el arreglo original.