El algoritmo de ordenamiento por mezcla (Merge Sort) no solo es una herramienta eficiente para organizar datos, sino que su estructura de "dividir y conquistar" permite resolver problemas complejos relacionados con el conteo de pares y rangos. La clave reside en aprovechar el momento en que dos subarreglos ya están ordenados para realizar cálculos que, de otro modo, requerirían una complejidad cuadrática.

Estructura base del algoritmo

Para implementar este patrón, partimos de la implementación clásica de Merge Sort. El objetivo es intervenir en el proceso de mezcla sin alterar la complejidad temporal de O(N log N).

public void ejecutarMergeSort(int[] datos, int inicio, int fin) {
    if (inicio >= fin) return;
    
    int puntoMedio = inicio + (fin - inicio) / 2;
    ejecutarMergeSort(datos, inicio, puntoMedio);
    ejecutarMergeSort(datos, puntoMedio + 1, fin);
    fusionar(datos, inicio, puntoMedio, fin);
}

private void fusionar(int[] datos, int izq, int medio, int der) {
    int[] temporal = new int[der - izq + 1];
    int i = izq, j = medio + 1, k = 0;

    while (i <= medio && j <= der) {
        temporal[k++] = datos[i] <= datos[j] ? datos[i++] : datos[j++];
    }
    while (i <= medio) temporal[k++] = datos[i++];
    while (j <= der) temporal[k++] = datos[j++];

    for (int p = 0; p < temporal.length; p++) {
        datos[izq + p] = temporal[p];
    }
}

Aplicación 1: Conteo de pares en reversa

Un problema común consiste en encontrar el número total de pares (i, j) tales que i < j y nums[i] > nums[j]. Utilizando la lógica de Merge Sort, podemos contar estas ocurrencias de forma eficiente.

Si durante la fase de mezcla detectamos que un elemento del subarreglo izquierdo es mayor que uno del derecho, debido a que ambos subarreglos están ordenados, todos los elementos restantes en la parte izquierda también serán mayores que ese elemento derecho.

public int calcularInversiones(int[] nums, int inicio, int fin) {
    if (inicio >= fin) return 0;
    int m = inicio + (fin - inicio) / 2;
    return calcularInversiones(nums, inicio, m) + 
           calcularInversiones(nums, m + 1, fin) + 
           mezclarYContar(nums, inicio, m, fin);
}

private int mezclarYContar(int[] arr, int l, int m, int r) {
    int[] aux = new int[r - l + 1];
    int p1 = l, p2 = m + 1, k = 0, total = 0;

    while (p1 <= m && p2 <= r) {
        if (arr[p1] > arr[p2]) {
            // Si arr[p1] > arr[p2], todos desde p1 hasta m son mayores que arr[p2]
            total += (m - p1 + 1);
            aux[k++] = arr[p2++];
        } else {
            aux[k++] = arr[p1++];
        }
    }
    while (p1 <= m) aux[k++] = arr[p1++];
    while (p2 <= r) aux[k++] = arr[p2++];
    System.arraycopy(aux, 0, arr, l, aux.length);
    return total;
}

Aplicación 2: Sumas de rangos en un intervalo [lower, upper]

Este es un reto de nivel avanzado. Dado un arreglo, debemos encontrar cuántos subarreglos tienen una suma que cae dentro de un rango específico. La solución óptima implica transformar el problema utilizando sumas prefijas.

Si definimos S[i] como la suma de los primeros i elementos, la suma del subarreglo entre j y i es S[i] - S[j-1]. Buscamos: lower ≤ S[i] - S[j-1] ≤ upper, lo cual es equivalente a S[i] - upper ≤ S[j-1] ≤ S[i] - lower.

public int countRangeSum(int[] nums, int lower, int upper) {
    int n = nums.length;
    long[] prefijos = new long[n + 1];
    for (int i = 0; i < n; i++) {
        prefijos[i + 1] = prefijos[i] + nums[i];
    }
    return recursiónConteo(prefijos, 0, n, lower, upper);
}

private int recursiónConteo(long[] sumas, int izq, int der, int low, int upp) {
    if (izq >= der) return 0;
    int mid = izq + (der - izq) / 2;
    int conteo = recursiónConteo(sumas, izq, mid, low, upp) + 
                 recursiónConteo(sumas, mid + 1, der, low, upp);

    // Conteo mediante ventana deslizante sobre subarreglos ordenados
    int ventanaInicio = izq, ventanaFin = izq;
    for (int j = mid + 1; j <= der; j++) {
        long minRequerido = sumas[j] - upp;
        long maxRequerido = sumas[j] - low;
        while (ventanaFin <= mid && sumas[ventanaFin] <= maxRequerido) {
            ventanaFin++;
        }
        while (ventanaInicio <= mid && sumas[ventanaInicio] < minRequerido) {
            ventanaInicio++;
        }
        conteo += (ventanaFin - ventanaInicio);
    }

    // Proceso de mezcla estándar
    long[] temp = new long[der - izq + 1];
    int idx1 = izq, idx2 = mid + 1, t = 0;
    while (idx1 <= mid && idx2 <= der) {
        temp[t++] = sumas[idx1] <= sumas[idx2] ? sumas[idx1++] : sumas[idx2++];
    }
    while (idx1 <= mid) temp[t++] = sumas[idx1++];
    while (idx2 <= der) temp[t++] = sumas[idx2++];
    System.arraycopy(temp, 0, sumas, izq, temp.length);

    return conteo;
}

Análisis del patrón de resolución

Para determinar si un problema es apto para este enfoque, debemos evaluar si la condición solicitada puede expresarse como una relación entre elementos de dos grupos (izquierdo y derecho) una vez que estos han sido procesados individualmente. Las preguntas clave son:

• ¿La relación depende del orden original de los índices?
• ¿Podemos usar prefijos o transformaciones para convertir el problema en una búsqueda de rangos?
• ¿El uso de punteros o ventanas deslizantes sobre subarreglos ordenados reduce la complejidad?

Al dominar esta técnica, problemas que parecen requerir fuerza bruta pueden resolverse de manera eficiente, aprovechando la naturaleza intrínseca de los algoritmos de ordenamiento estables y su capacidad para procesar información durante la etapa de combinación.