El ordenamiento por mezcla es un algoritmo de ordenación basado en la estrategia divide y vencerás. El procedimiento consiste en dividir repetidamente el arreglo en mitades hasta que cada subarreglo contenga un único elemento, y después fusionar esos subarreglos de forma ordenada.

La idea clave se apoya en dos operaciones:

• Dividir: partir el arreglo por la mitad de manera recursiva.
• Mezclar: combinar dos subarreglos ya ordneados en uno solo, seleciconando siempre el menor de los dos elementos disponibles.

La complejidad temporal del algoritmo es O(n log n) tento en el caso promedio como en el peor caso, y es un ordenamiento estable si se implementa conservando el orden relativo de los elementos iguales.

A continuación se muestra una implementación en C# que utiliza arreglos e índices en lugar de estructuras auxiliares como colas o nodos:

using System;

public static class OrdenamientoPorMezcla
{
    public static int[] Ordenar(int[] valores)
    {
        if (valores == null || valores.Length <= 1)
            return valores;

        return OrdenarSubArreglo(valores, 0, valores.Length - 1);
    }

    private static int[] OrdenarSubArreglo(int[] datos, int inicio, int fin)
    {
        if (inicio == fin)
            return new int[] { datos[inicio] };

        int medio = inicio + (fin - inicio) / 2;

        int[] izquierda = OrdenarSubArreglo(datos, inicio, medio);
        int[] derecha = OrdenarSubArreglo(datos, medio + 1, fin);

        return Mezclar(izquierda, derecha);
    }

    private static int[] Mezclar(int[] izquierda, int[] derecha)
    {
        int total = izquierda.Length + derecha.Length;
        int[] resultado = new int[total];

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

        while (i < izquierda.Length && j < derecha.Length)
        {
            if (izquierda[i] <= derecha[j])
                resultado[k++] = izquierda[i++];
            else
                resultado[k++] = derecha[j++];
        }

        while (i < izquierda.Length)
            resultado[k++] = izquierda[i++];

        while (j < derecha.Length)
            resultado[k++] = derecha[j++];

        return resultado;
    }
}

Para utilizar el ordenamiento, basta con invocar al método Ordenar y mostrar el resultado:

static void Main(string[] args)
{
    int[] datos = { 12, 4, 6, 3, 20, 7, 4 };
    int[] ordenados = OrdenamientoPorMezcla.Ordenar(datos);

    Console.WriteLine(string.Join(", ", ordenados));
    // Salida: 3, 4, 4, 6, 7, 12, 20
}