Merge Sort

Categoría: Sorting

El problema

El Bubble Sort y el Insertion Sort de este repositorio son ambos adaptativos — genuinamente rápidos con entradas casi ordenadas —, pero esa adaptabilidad es justo lo que los convierte en un riesgo en el momento en que no se puede confiar en el orden de la entrada: ambos degradan a O(n²) con la entrada equivocada, de forma impredecible, sin ninguna protección. Un lote grande, o uno cuyo orden un adversario pudiera influenciar, necesita una cota que se mantenga sin importar cómo llegue la entrada — no un mejor caso que solo compensa cuando tienes suerte.

La solución

Divide el array por la mitad, ordena recursivamente cada mitad y luego combina (merge) las dos mitades ya ordenadas en una sola. La división llega a su fondo en elementos individuales (trivialmente ordenados); combinar dos secuencias ordenadas solo necesita comparar sus cabezas actuales y tomar la menor, que es justo lo que hace que el propio paso de merge sea lineal. Como el punto de división siempre es el punto medio — y no depende de los datos, a diferencia del Quick Sort de este repositorio —, la profundidad de la recursión es siempre exactamente log2(n), y cada nivel hace O(n) de trabajo total de merge: O(n log n), incondicionalmente, sin que el orden de la entrada tenga voto. El único costo real: el merge necesita un buffer auxiliar, así que esto es O(n) de espacio extra, no es in-place. Tomar siempre de la mitad izquierda cuando el comparador reporta un empate es también lo que hace que esta ordenación sea estable — los elementos iguales mantienen su orden relativo original.

flowchart TB
    subgraph "split"
        direction TB
        S0["[5,3,8,1]"] --> S1["[5,3]"] & S2["[8,1]"]
        S1 --> S3["[5]"] & S4["[3]"]
        S2 --> S5["[8]"] & S6["[1]"]
    end
    subgraph "merge back up"
        direction TB
        M4["[5]"] & M3["[3]"] --> M1["[3,5]"]
        M6["[1]"] & M5["[8]"] --> M2["[1,8]"]
        M1 --> M0["[1,3,5,8]"]
        M2 --> M0
    end

Ejemplo clásico

classic/MergeSort es genérico sobre Comparator<? super T> — sin atajo mediante Arrays.sort/Collections.sort. Se asigna un único buffer Object[] una vez al principio y se reutiliza a lo largo de toda la recursión (solo el subrango relevante se copia en él en cada merge), en lugar de asignar un array nuevo en cada llamada recursiva. MergeSortTest cubre un array desordenado, ya ordenado, ordenado en reversa, un array de tamaño impar (ejercita la división desigual), un array de un solo elemento y uno vacío, un comparador personalizado (descendente), las dos protecciones contra argumento nulo y — probando directamente la afirmación de estabilidad — una prueba con elementos etiquetados que ordena por un valor que tiene duplicados y verifica que los duplicados mantienen su orden relativo original.

Ejemplo aplicado: ordenamiento de reportes de compliance por fraude

applied/ComplianceReportSort ordena las transacciones marcadas por fraude según el puntaje de riesgo, de mayor a menor, para un reporte de compliance que debe ser reproducible ejecución tras ejecución: la misma entrada siempre debe producir exactamente el mismo orden de salida, incluyendo cómo se resuelven los empates en el puntaje de riesgo. El peor caso garantizado de O(n log n) del merge sort protege contra la degradación impredecible de un lote grande y con muchos puntajes duplicados, y su estabilidad hace que las transacciones con el mismo puntaje mantengan el orden en que fueron marcadas originalmente — un auditor que vuelva a ejecutar este reporte más tarde obtiene un resultado idéntico, no solo uno igualmente válido. ComplianceReportSortTest cubre el orden descendente por puntaje, los empates preservando el orden original de marcado, que el array de entrada queda intacto, y la protección contra argumento nulo.

Benchmark

./gradlew :sorting:merge-sort:jmh

Ejecución real en esta máquina (JMH 1.37, JDK 26.0.2, 2 iteraciones de warmup + 3 de medición, 1 fork). Mismos tres órdenes y tamaños que los benchmarks de Bubble Sort e Insertion Sort de este repositorio — el objetivo aquí es el contraste:

Ya-ordenado y casi-ordenado se comportan de forma casi idéntica en todos los tamaños — el orden de la entrada realmente no importa aquí, a diferencia de las brechas de más de 1,000x que Bubble Sort y Insertion Sort muestran entre sus mejores y peores casos en esta misma máquina. El caso aleatorio es consistentemente el más costoso de los tres, pero solo por aproximadamente 1.8–2x, no órdenes de magnitud — trabajo real, no un caso degenerado. Y la forma de crecimiento entre tamaños confirma O(n log n), no O(n²): al pasar de size=1,000 a size=10,000 (10x los datos), el caso aleatorio cuesta ~11.7x más — cerca del ~13.3x que predice una forma O(n log n) para ese salto (10,000·log₂(10,000) ÷ 1,000·log₂(1,000)), lejos del ~100x que mostraría una ordenación cuadrática para el mismo incremento de tamaño.

Cuándo no usarlo

• ¿Presupuesto de memoria ajustado, o necesitas una ordenación genuinamente in-place? El buffer auxiliar O(n) del merge sort es el único costo real de su cota garantizada — el Quick Sort o el Heap Sort de este repositorio ordenan in-place en su lugar.
• ¿La entrada es pequeña y ya está cerca de ordenada? El factor constante más bajo del Insertion Sort gana a esa escala — el propio benchmark de este módulo muestra que el merge sort paga aproximadamente el mismo costo esté la entrada ordenada o no, que es justamente el punto, pero no es gratis.
• ¿No necesitas realmente la garantía de estabilidad y quieres el mejor factor constante de caso promedio en la práctica? El Quick Sort suele superar al merge sort en tiempo de reloj (wall-clock) con entradas típicas (no adversariales), a costa de perder la garantía de peor caso que ofrece este módulo.

Cobertura de pruebas

100% de cobertura de instrucciones, 100% de cobertura de ramas (JaCoCo). Reprodúcelo tú mismo:

./gradlew :sorting:merge-sort:jacocoTestReport

Reporte en sorting/merge-sort/build/reports/jacoco/test/html/index.html.

Lectura complementaria

• Cormen, Leiserson, Rivest & Stein — Introduction to Algorithms (CLRS), 3.ª/4.ª ed., Capítulo 2.3, "Designing algorithms" — el merge sort es el ejemplo canónico de divide y vencerás de CLRS, con la recurrencia T(n) = 2T(n/2) + O(n) cuya forma en el mundo real mide el benchmark de este módulo.
• Sedgewick & Wayne — Algorithms, 4.ª ed., Capítulo 2.2, "Mergesort" — incluye la variante bottom-up (no recursiva) como contraste con la versión recursiva top-down implementada aquí.

Pruebas unitarias

package com.algorithms.sorting.mergesort.classic;

import org.junit.jupiter.api.Test;

import java.util.Comparator;

import static org.assertj.core.api.Assertions.assertThat;
import static org.assertj.core.api.Assertions.assertThatThrownBy;

class MergeSortTest {

    @Test
    void sortsAnUnorderedArrayIntoAscendingOrder() {
        Integer[] array = {5, 3, 8, 1, 9, 2};

        MergeSort.sort(array, Comparator.naturalOrder());

        assertThat(array).containsExactly(1, 2, 3, 5, 8, 9);
    }

    @Test
    void alreadySortedArrayStaysSorted() {
        Integer[] array = {1, 2, 3, 4, 5};

        MergeSort.sort(array, Comparator.naturalOrder());

        assertThat(array).containsExactly(1, 2, 3, 4, 5);
    }

    @Test
    void reverseSortedArrayEndsUpAscending() {
        Integer[] array = {5, 4, 3, 2, 1};

        MergeSort.sort(array, Comparator.naturalOrder());

        assertThat(array).containsExactly(1, 2, 3, 4, 5);
    }

    @Test
    void oddSizedArraySortsCorrectly() {
        Integer[] array = {9, 4, 7, 1, 3};

        MergeSort.sort(array, Comparator.naturalOrder());

        assertThat(array).containsExactly(1, 3, 4, 7, 9);
    }

    @Test
    void singleElementArrayStaysUnchanged() {
        Integer[] array = {42};

        MergeSort.sort(array, Comparator.naturalOrder());

        assertThat(array).containsExactly(42);
    }

    @Test
    void emptyArrayStaysEmpty() {
        Integer[] array = {};

        MergeSort.sort(array, Comparator.naturalOrder());

        assertThat(array).isEmpty();
    }

    @Test
    void sortsUsingACustomComparatorForDescendingOrder() {
        Integer[] array = {1, 5, 3, 2, 4};

        MergeSort.sort(array, Comparator.reverseOrder());

        assertThat(array).containsExactly(5, 4, 3, 2, 1);
    }

    @Test
    void isStableElementsTiedOnTheComparatorKeepTheirOriginalRelativeOrder() {
        record Tagged(int value, int originalIndex) {
        }
        Tagged[] array = {
                new Tagged(1, 0),
                new Tagged(2, 1),
                new Tagged(1, 2),
                new Tagged(2, 3),
        };

        MergeSort.sort(array, Comparator.comparingInt(Tagged::value));

        assertThat(array).extracting(Tagged::originalIndex).containsExactly(0, 2, 1, 3);
    }

    @Test
    void rejectsANullArray() {
        assertThatThrownBy(() -> MergeSort.sort(null, Comparator.naturalOrder()))
                .isInstanceOf(IllegalArgumentException.class);
    }

    @Test
    void rejectsANullComparator() {
        assertThatThrownBy(() -> MergeSort.sort(new Integer[] {1, 2}, null))
                .isInstanceOf(IllegalArgumentException.class);
    }
}

package com.algorithms.sorting.mergesort.applied;

import org.junit.jupiter.api.Test;

import java.time.Instant;

import static org.assertj.core.api.Assertions.assertThat;
import static org.assertj.core.api.Assertions.assertThatThrownBy;

class ComplianceReportSortTest {

    private static final Instant WHEN = Instant.parse("2026-08-17T09:00:00Z");

    @Test
    void sortByRiskScoreDescendingOrdersHighestFirst() {
        ComplianceReportSort sorter = new ComplianceReportSort();
        FlaggedTransaction[] transactions = {
                transaction("low", 20),
                transaction("high", 90),
                transaction("mid", 55),
        };

        FlaggedTransaction[] sorted = sorter.sortByRiskScoreDescending(transactions);

        assertThat(sorted).extracting(FlaggedTransaction::transactionId).containsExactly("high", "mid", "low");
    }

    @Test
    void tiesOnRiskScorePreserveOriginalFlaggingOrder() {
        ComplianceReportSort sorter = new ComplianceReportSort();
        FlaggedTransaction[] transactions = {
                transaction("first-flagged", 70),
                transaction("second-flagged", 70),
                transaction("third-flagged", 70),
        };

        FlaggedTransaction[] sorted = sorter.sortByRiskScoreDescending(transactions);

        assertThat(sorted).extracting(FlaggedTransaction::transactionId)
                .containsExactly("first-flagged", "second-flagged", "third-flagged");
    }

    @Test
    void doesNotMutateTheInputArray() {
        ComplianceReportSort sorter = new ComplianceReportSort();
        FlaggedTransaction[] transactions = {transaction("b", 10), transaction("a", 90)};

        sorter.sortByRiskScoreDescending(transactions);

        assertThat(transactions).extracting(FlaggedTransaction::transactionId).containsExactly("b", "a");
    }

    @Test
    void rejectsNullTransactions() {
        ComplianceReportSort sorter = new ComplianceReportSort();

        assertThatThrownBy(() -> sorter.sortByRiskScoreDescending(null)).isInstanceOf(IllegalArgumentException.class);
    }

    private static FlaggedTransaction transaction(String id, int riskScore) {
        return new FlaggedTransaction(id, riskScore, WHEN);
    }
}

Ver informe completo de cobertura JaCoCo →