Los algoritmos de ordenamiento con complejidad temporal O(n log n) son esenciales en informática, y tanto el ordenamiento por mezcla como el rápido emplean el paradigma de divide y vencerás. Este enfoque divide un problema en subproblemas más manejables que se resuelven recursivamente, facilitando así la solución del problema original.

Ordenamiento por Mezcla (Merge Sort)

Este algoritmo ordena un arreglo dividiéndolo en dos mitades, ordenando recursivamente cada una y luego fusionándolas en un único arreglo ordenado.

La recursión se define mediante una fórmula como mezcla_ordenar(p...r) = fusionar(mezcla_ordenar(p...q), mezcla_ordenar(q+1...r)), donde q es el punto medio calculado como (p + r) / 2. El caso base ocurre cuando p >= r, lo que significa que el subarreglo ya está ordenado o es trivial.

La función de fusión combina dos subarreglos preordenados. Utiliza un arreglo auxiliar temporal y dos índices para comparar y copiar elementos en orden, asegurando que el resultado final esté ordenado.

Implementación en C con variables renombradas y estructura modificada:

void fusionar(int arr[], int aux[], int izq, int medio, int der) {
    int i = izq, j = medio + 1, k = izq;
    while (i <= medio && j <= der) {
        if (arr[i] <= arr[j]) {
            aux[k++] = arr[i++];
        } else {
            aux[k++] = arr[j++];
        }
    }
    while (i <= medio) {
        aux[k++] = arr[i++];
    }
    while (j <= der) {
        aux[k++] = arr[j++];
    }
    for (int idx = izq; idx <= der; idx++) {
        arr[idx] = aux[idx];
    }
}

void ordenamiento_mezcla(int arr[], int aux[], int izq, int der) {
    if (izq < der) {
        int medio = izq + (der - izq) / 2;
        ordenamiento_mezcla(arr, aux, izq, medio);
        ordenamiento_mezcla(arr, aux, medio + 1, der);
        fusionar(arr, aux, izq, medio, der);
    }
}

Aspectos importantes del ordenamiento por mezcla:

• Es un algoritmo estable, ya que mantiene el orden relativo de elementos con valores iguales.
• La complejidad temporal es O(n log n) en el mejor, peor y caso promedio.
• No es in situ, ya que requiere un arreglo auxiliar con complejidad espacial O(n).

Ordenamiento Rápido (Quick Sort)

Este método selecciona un pivote y reorganiza el arreglo de modo que los elementos menores que el pivote queden a la izquierda y los mayores a la derecha, luego aplica recursión a los subarreglos resultantes.

La recursión se expresa como rapido_ordenar(p...r) = rapido_ordenar(p...q-1) + rapido_ordenar(q+1...r), donde q es el índice del pivote tras la partición. El caso base es p >= r.

La función de partición reorganiza el arreglo alrededor del pivote, devolviendo su posición final.

Implementación en C con cambios en nombres de variables y lógica:

void intercambiar(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

int particionar(int arr[], int inicio, int fin) {
    int pivote = arr[inicio];
    int i = fin;
    for (int j = fin; j > inicio; j--) {
        if (arr[j] > pivote) {
            intercambiar(&arr[i], &arr[j]);
            i--;
        }
    }
    intercambiar(&arr[i], &arr[inicio]);
    return i;
}

void ordenamiento_rapido(int arr[], int inicio, int fin) {
    if (inicio < fin) {
        int q = particionar(arr, inicio, fin);
        ordenamiento_rapido(arr, inicio, q - 1);
        ordenamiento_rapido(arr, q + 1, fin);
    }
}

Características del ordenamiento rápido:

• Es un algoritmo in situ, ya que no necesita espacio adicional significativo más allá de la pila de recursión.
• No es estable, ya que puede alterar el orden relativo de elementos iguales.
• La complejidad temporal varía: O(n log n) en el mejor y caso promedio, pero puede degradarse a O(n²) en el peor caso si la selección del pivote es desfavorable.