CodeUtility
Haz que programar sea más fácil.
Algoritmos en C/C++

El ordenamiento por mezcla (merge sort) en C y C++

En esta lección vas a implementar el ordenamiento por mezcla con la estrategia divide y vencerás, que siempre se ejecuta en O(n log n).

Introducción

El ordenamiento por mezcla parte el arreglo en dos mitades, ordena cada una con una llamada recursiva y luego mezcla las dos mitades ordenadas en una secuencia ordenada. Su gran ventaja es un tiempo de ejecución siempre estable en O(n log n), sea cual sea el estado de los datos de entrada.

Puntos importantes

  • Prueba con una entrada vacía, un solo elemento, valores repetidos y datos ya ordenados.
  • Primero haz que el código sea correcto y después optimízalo.
  • En código real, usa preferentemente las funciones ya hechas de la biblioteca estándar.

Visualizador de El ordenamiento por mezcla (merge sort) en C y C++

O(n)

Usa Reproducir o Paso para seguir cada comparación y movimiento de datos.

Ejemplos de código C y C++

C
Ejecutar →
main.c
#include <stdio.h>
#include <stdlib.h>

void merge_sort(int *values, int *temporary, int left, int right) {
    if (right - left < 2) return;
    int middle = (left + right) / 2;
    merge_sort(values, temporary, left, middle);
    merge_sort(values, temporary, middle, right);

    int first = left;
    int second = middle;
    int output = left;
    while (first < middle && second < right) {
        temporary[output++] = values[first] < values[second]
            ? values[first++] : values[second++];
    }
    while (first < middle) temporary[output++] = values[first++];
    while (second < right) temporary[output++] = values[second++];
    for (int index = left; index < right; ++index) {
        values[index] = temporary[index];
    }
}

int main(void) {
    int values[] = {8, 3, 6, 2, 7};
    int temporary[5];
    merge_sort(values, temporary, 0, 5);
    for (int index = 0; index < 5; ++index) {
        printf("%d ", values[index]);
    }
}
Resultado de la ejecución
2 3 6 7 8
C++
Ejecutar →
main.cpp
#include <algorithm>
#include <iostream>
#include <vector>

void merge_sort(std::vector<int>& values) {
    if (values.size() < 2) return;
    auto middle = values.begin() + values.size() / 2;
    std::vector<int> left(values.begin(), middle);
    std::vector<int> right(middle, values.end());
    merge_sort(left);
    merge_sort(right);
    std::merge(left.begin(), left.end(), right.begin(), right.end(),
               values.begin());
}

int main() {
    std::vector values{8, 3, 6, 2, 7};
    merge_sort(values);
    for (int value : values) {
        std::cout << value << ' ';
    }
}
Resultado de la ejecución
2 3 6 7 8

Comparación entre C y C++

La función merge_sort en C se detiene cuando el tramo tiene menos de 2 elementos. Tras ordenar las dos mitades, el bucle while elige cada vez el menor de los dos elementos del principio y lo copia en el arreglo temporal temporary, y después copia lo que queda. Las dos versiones necesitan O(n) de memoria adicional. La versión de C gestiona ella misma el arreglo temporal, y la de C++ usa vector y los algoritmos estándar para un código más claro.

C

Los bucles, los punteros, las longitudes y los búferes temporales se escriben de forma explícita.

C++

Los iteradores y los algoritmos estándar separan el procesamiento de la forma en que se guardan los datos.

Ejercicios de práctica

Ejecuta las dos versiones y después modifica el código para ver la diferencia de seguridad que aporta cada lenguaje.

  • Sigue cada comparación en papel.
  • Prueba con valores repetidos y con valores muy grandes y muy pequeños.
  • Mide el tiempo de ejecución de tu código y compáralo con la biblioteca estándar.

Practica con un reto

Usa lo que cubre esta lección para resolver un problema real. Cada reto se ejecuta en el navegador, con pruebas al instante y una revisión de IA.

Todos los retos