Divide y vencerás en Java: algoritmos recursivos con ejemplos

         [5, 3, 8, 1, 4, 7, 2, 6]          ← Problema original
                /              \
       [5, 3, 8, 1]      [4, 7, 2, 6]       ← DIVIDIR
        /        \          /        \
    [5, 3]    [8, 1]    [4, 7]    [2, 6]     ← DIVIDIR
    /   \     /   \     /   \     /   \
  [5]  [3]  [8]  [1]  [4]  [7]  [2]  [6]    ← CASO BASE

  [3,5]    [1,8]    [4,7]    [2,6]           ← COMBINAR (mezclar)
     [1, 3, 5, 8]      [2, 4, 6, 7]         ← COMBINAR
         [1, 2, 3, 4, 5, 6, 7, 8]           ← SOLUCIÓN

/**
 * Plantilla genérica de divide y vencerás.
 * @param problema  el problema (o porción) a resolver
 * @return          la solución al problema
 */
public Solucion divideYVenceras(Problema problema) {

    // 1. CASO BASE: si el problema es lo bastante pequeño, resolverlo directamente
    if (esCasoBase(problema)) {
        return resolverDirectamente(problema);
    }

    // 2. DIVIDIR: descomponer en subproblemas
    Problema[] subproblemas = dividir(problema);

    // 3. CONQUISTAR: resolver cada subproblema recursivamente
    Solucion[] soluciones = new Solucion[subproblemas.length];
    for (int i = 0; i < subproblemas.length; i++) {
        soluciones[i] = divideYVenceras(subproblemas[i]);
    }

    // 4. COMBINAR: fusionar las soluciones parciales
    return combinar(soluciones);
}

public class BusquedaBinaria {

    /**
     * Busca un valor en un array ordenado usando divide y vencerás.
     * @param arr   array ordenado de enteros
     * @param valor el valor a buscar
     * @param izq   índice izquierdo del rango actual
     * @param der   índice derecho del rango actual
     * @return      índice del valor, o -1 si no se encuentra
     */
    public static int buscar(int[] arr, int valor, int izq, int der) {

        // CASO BASE: rango vacío → no encontrado
        if (izq > der) {
            return -1;
        }

        // DIVIDIR: calcular el punto medio
        int medio = izq + (der - izq) / 2;  // Evita overflow con (izq+der)/2

        // CONQUISTAR: comparar y elegir la mitad correcta
        if (arr[medio] == valor) {
            return medio;                           // ¡Encontrado!
        } else if (valor < arr[medio]) {
            return buscar(arr, valor, izq, medio - 1);  // Buscar en mitad izquierda
        } else {
            return buscar(arr, valor, medio + 1, der);  // Buscar en mitad derecha
        }
        // COMBINAR: no es necesario (solo hay un subproblema)
    }

    public static void main(String[] args) {
        int[] datos = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
        int objetivo = 23;

        int indice = buscar(datos, objetivo, 0, datos.length - 1);

        if (indice >= 0) {
            System.out.println("Valor " + objetivo + " encontrado en índice " + indice);
        } else {
            System.out.println("Valor " + objetivo + " no encontrado");
        }
    }
}

Valor 23 encontrado en índice 5

public class MergeSort {

    /**
     * Ordena un array de enteros usando MergeSort.
     * @param arr array a ordenar
     * @param izq índice izquierdo (inclusivo)
     * @param der índice derecho (inclusivo)
     */
    public static void mergeSort(int[] arr, int izq, int der) {

        // CASO BASE: un solo elemento o rango vacío → ya está ordenado
        if (izq >= der) {
            return;
        }

        // DIVIDIR: calcular el punto medio
        int medio = izq + (der - izq) / 2;

        // CONQUISTAR: ordenar recursivamente cada mitad
        mergeSort(arr, izq, medio);       // Mitad izquierda
        mergeSort(arr, medio + 1, der);   // Mitad derecha

        // COMBINAR: mezclar las dos mitades ordenadas
        merge(arr, izq, medio, der);
    }

    /**
     * Mezcla dos subarrays ordenados: arr[izq..medio] y arr[medio+1..der].
     */
    private static void merge(int[] arr, int izq, int medio, int der) {

        // Crear copias temporales de las dos mitades
        int n1 = medio - izq + 1;
        int n2 = der - medio;
        int[] izqArr = new int[n1];
        int[] derArr = new int[n2];

        System.arraycopy(arr, izq, izqArr, 0, n1);
        System.arraycopy(arr, medio + 1, derArr, 0, n2);

        // Mezclar comparando elemento a elemento
        int i = 0, j = 0, k = izq;
        while (i < n1 && j < n2) {
            if (izqArr[i] <= derArr[j]) {
                arr[k++] = izqArr[i++];
            } else {
                arr[k++] = derArr[j++];
            }
        }

        // Copiar elementos restantes (si los hay)
        while (i < n1) arr[k++] = izqArr[i++];
        while (j < n2) arr[k++] = derArr[j++];
    }

    public static void main(String[] args) {
        int[] datos = {38, 27, 43, 3, 9, 82, 10};
        System.out.println("Original:  " + java.util.Arrays.toString(datos));

        mergeSort(datos, 0, datos.length - 1);

        System.out.println("Ordenado:  " + java.util.Arrays.toString(datos));
    }
}

Original:  [38, 27, 43, 3, 9, 82, 10]
Ordenado:  [3, 9, 10, 27, 38, 43, 82]

public class QuickSort {

    /**
     * Ordena un array de enteros usando QuickSort.
     */
    public static void quickSort(int[] arr, int izq, int der) {

        // CASO BASE: rango de 0 o 1 elementos
        if (izq >= der) {
            return;
        }

        // DIVIDIR + COMBINAR: particionar alrededor del pivote
        int indicePivote = particionar(arr, izq, der);

        // CONQUISTAR: ordenar recursivamente cada partición
        quickSort(arr, izq, indicePivote - 1);   // Menores que pivote
        quickSort(arr, indicePivote + 1, der);    // Mayores que pivote
    }

    /**
     * Partición de Lomuto: usa el último elemento como pivote.
     * Coloca todos los menores a la izquierda del pivote
     * y todos los mayores a la derecha.
     * @return el índice final del pivote
     */
    private static int particionar(int[] arr, int izq, int der) {
        int pivote = arr[der];  // Elegir último elemento como pivote
        int i = izq - 1;       // Frontera de los elementos menores

        for (int j = izq; j < der; j++) {
            if (arr[j] <= pivote) {
                i++;
                intercambiar(arr, i, j);
            }
        }

        // Colocar el pivote en su posición final
        intercambiar(arr, i + 1, der);
        return i + 1;
    }

    private static void intercambiar(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        int[] datos = {10, 80, 30, 90, 40, 50, 70};
        System.out.println("Original:  " + java.util.Arrays.toString(datos));

        quickSort(datos, 0, datos.length - 1);

        System.out.println("Ordenado:  " + java.util.Arrays.toString(datos));
    }
}

Original:  [10, 80, 30, 90, 40, 50, 70]
Ordenado:  [10, 30, 40, 50, 70, 80, 90]

T(n) = a · T(n/b) + f(n)

Donde:
  a = número de subproblemas generados en cada división
  b = factor por el que se reduce el tamaño del problema
  f(n) = coste de dividir + combinar

import java.util.concurrent.RecursiveAction;
import java.util.concurrent.ForkJoinPool;

public class MergeSortParalelo extends RecursiveAction {

    private static final int UMBRAL = 1024; // Debajo de este tamaño, usar sort secuencial
    private final int[] arr;
    private final int izq, der;

    public MergeSortParalelo(int[] arr, int izq, int der) {
        this.arr = arr;
        this.izq = izq;
        this.der = der;
    }

    @Override
    protected void compute() {
        // Caso base: si es pequeño, ordenar secuencialmente
        if (der - izq < UMBRAL) {
            java.util.Arrays.sort(arr, izq, der + 1);
            return;
        }

        // Dividir
        int medio = izq + (der - izq) / 2;

        // Crear subtareas
        MergeSortParalelo tareaIzq = new MergeSortParalelo(arr, izq, medio);
        MergeSortParalelo tareaDer = new MergeSortParalelo(arr, medio + 1, der);

        // Fork: lanzar la tarea izquierda en otro hilo
        tareaIzq.fork();

        // Ejecutar la tarea derecha en el hilo actual
        tareaDer.compute();

        // Join: esperar a que termine la tarea izquierda
        tareaIzq.join();

        // Combinar: mezclar las dos mitades ordenadas
        merge(arr, izq, medio, der);
    }

    private void merge(int[] arr, int izq, int medio, int der) {
        int[] temp = new int[der - izq + 1];
        int i = izq, j = medio + 1, k = 0;
        while (i <= medio && j <= der) {
            temp[k++] = (arr[i] <= arr[j]) ? arr[i++] : arr[j++];
        }
        while (i <= medio) temp[k++] = arr[i++];
        while (j <= der)   temp[k++] = arr[j++];
        System.arraycopy(temp, 0, arr, izq, temp.length);
    }

    public static void main(String[] args) {
        int[] datos = new int[1_000_000];
        java.util.Random rng = new java.util.Random(42);
        for (int i = 0; i < datos.length; i++) datos[i] = rng.nextInt();

        long inicio = System.nanoTime();
        ForkJoinPool pool = ForkJoinPool.commonPool();
        pool.invoke(new MergeSortParalelo(datos, 0, datos.length - 1));
        long fin = System.nanoTime();

        System.out.println("Ordenados " + datos.length + " elementos en "
                         + (fin - inicio) / 1_000_000 + " ms");
        System.out.println("¿Ordenado correctamente? "
                         + estaOrdenado(datos));
    }

    private static boolean estaOrdenado(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] < arr[i - 1]) return false;
        }
        return true;
    }
}