Taller - meruiz22/Analisis-de-Algoritmos GitHub Wiki

Algoritmo merge

Código en java

public class MergeSortExample {

    public static void merge(int[] A, int p, int q, int r) {
        int nL = q - p + 1;
        int nR = r - q;

        int[] L = new int[nL];
        int[] R = new int[nR];

        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];
        }

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

        while (i < nL && j < nR) {
            if (L[i] <= R[j]) {
                A[k] = L[i];
                i++;
            } else {
                A[k] = R[j];
                j++;
            }
            k++;
        }

        while (i < nL) {
            A[k] = L[i];
            i++;
            k++;
        }

        while (j < nR) {
            A[k] = R[j];
            j++;
            k++;
        }
    }

    public static void main(String[] args) {
        int[] A = {4, 7, 9, 1, 3, 6}; // Segmento ordenado A[0..2] y A[3..5]

        System.out.println("Antes de MERGE:");
        printArray(A);

        // Aplicamos merge sobre A[0..2] y A[3..5]
        merge(A, 0, 2, 5);

        System.out.println("Después de MERGE:");
        printArray(A);
    }

    public static void printArray(int[] A) {
        for (int value : A) {
            System.out.print(value + " ");
        }
        System.out.println();
    }
}