¿Cómo funciona la ordenación por fusión en C ++?

Funciona exactamente de la misma manera que la combinación de clasificación funciona en cualquier otro idioma. Cualquier implementación que vea en cualquier otro lenguaje o, incluso, en pseudocódigo, se traduce casi literalmente a C ++ con poca o ninguna diferencia algorítmica.

Existen varios enfoques diferentes para fusionar algoritmos de ordenación, que difieren, por ejemplo, en si se trata de fusiones en el lugar o fuera de lugar o si es estable (los elementos iguales permanecen en el mismo orden después de la ordenación), y así sucesivamente.

Funciona simplemente dividiendo conceptualmente una matriz en dos segmentos, recurriendo hacia abajo con el mismo algoritmo de clasificación de fusión y repitiendo el proceso hasta que el segmento que se está examinando sea lo suficientemente pequeño como para ordenarlo rápidamente, luego combina los resultados de ordenar cada subsegmento.

Por ejemplo, dada una matriz de 8 elementos:

{5, 3, 8, 6, 1, 9, 2, 4}

… La función mergesort se llama a sí misma en el rango de los primeros 4 elementos, luego nuevamente en los primeros dos. Los 5 y 3 se intercambian y esa llamada vuelve. Luego vuelve a aparecer en los siguientes dos elementos, intercambia los 8 y 6 y regresa. Luego “fusiona” estos resultados, recorriendo ambos segmentos y ordenándolos. Ya están ordenados, por lo que vuelve a la primera llamada.

Luego se llama a sí mismo en la segunda mitad de la matriz, luego nuevamente en la primera mitad de ese segmento, y así sucesivamente, y luego combina esos dos segmentos. “Fusiona” los resultados, probablemente copiándolos en otra matriz para ponerlos en orden. Tendrá un índice en el 1 y el 2, 1 es más pequeño, por lo que copia eso y avanza el primer índice al 9, 2 es más pequeño, por lo que copia eso y avanza el segundo índice al 4, y se repite hasta que la matriz se vea así:

{3, 5, 6, 8, 1, 2, 4, 9}

Luego regresa y la primera llamada combina las dos mitades ordenadas. 1 es menor que 3, copia, avance. 2 es menor que 3, copia, avance. 3 es menor que 4, copia, avance. Y así.