¿Cuál es la idea principal y las ventajas del algoritmo de ordenamiento por mezcla?

El algoritmo de ordenamiento por mezcla (Merge Sort) se basa en el principio de "divide y vencerás". Divide recursivamente el array original en dos mitades, ordena cada una de ellas y luego fusiona las dos partes ordenadas en un array ordenado.

Ventajas:

• Estabilidad: mantiene el orden de los elementos iguales.
• Tiempo de ejecución garantizado O(n log n) en el peor, medio y mejor caso.
• Adecuado para ordenar grandes volúmenes de datos y ordenamiento externo.

Ejemplo en Java:

void mergeSort(int[] arr, int left, int right) {
    if (left < right) {
        int mid = (left + right) / 2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
}

void merge(int[] arr, int left, int mid, int right) {
    // Lógica para fusionar dos subarreglos ordenados
}