Ordenación por Combinación - Merge Sort

El algoritmo de ordenación por combinación o Merge Sort, basado en la técnica Divide y Vencerás, ordena recursivamente un conjunto de elementos dividiéndolo en dos, ordenando cada una de estas partes en forma independiente y combinando los dos resultados.

Este código en el lenguaje de programación JAVA 1.6 recibe como entrada un arreglo de números enteros denominado v, lo parte utilizando el método copyOfRange de la clase java.util.Arrays, se llama recursivamente con cada una de las dos partes como argumento y, una vez terminada la ordenación de dichas partes, invoca al proceso de combinación de las dos respuestas implementado en el método combinar, el cual recibe como entrada el arreglo original y las dos mitades del mismo previamente ordenadas que serán combinadas en el arreglo original.

// Algoritmo de ordenacion por combinacion: Merge Sort
    public static void ordenacionCombinacion(int[] v) {
        final int N = v.length;
        if(N<=1) return;
        int mitad=N/2;
        int[] izq = Arrays.copyOfRange(v, 0, mitad);
        int[] der = Arrays.copyOfRange(v, mitad, N);
        ordenacionCombinacion(izq);
        ordenacionCombinacion(der);
        combinar(v, izq, der);
    }

    public static void combinar(int[] resp, int[] izq, int[] der) {
        int i = 0;
        int j = 0;
        for(int k=0; k<resp.length;k++) {
            if(i>=izq.length) { resp[k]=der[j++]; continue; }
            if(j>=der.length) { resp[k]=izq[i++]; continue; }
            resp[k]=(izq[i]<der[j])?izq[i++]:der[j++];
        }
    }

Este algoritmo tiene complejidad O(n log n), que se obtiene resolviendo la ecuación de recurrencias T(n) = k n + 2 T(n/2).  La solución a la misma se puede comprobar gracias a la tecnologías del sitio WolframAlpha