Ordenación por fusión

Ordenación por fusión

Ejemplo de ordenación por combinación. Primero, se divide la lista en la unidad más pequeña (1 elemento) y luego se compara cada elemento con la lista adyacente para ordenar y combinar las dos listas adyacentes. Finalmente, se ordenan y combinan todos los elementos.
Clase	Algoritmo de ordenación
Estructura de datos	Formación
Rendimiento en el peor de los casos	${\displaystyle O(n\log n)}$
Rendimiento en el mejor de los casos	${\displaystyle \Omega (n\log n)}$variante típica y natural${\displaystyle \Omega (n)}$
Rendimiento promedio	${\displaystyle \Theta(n\log n)}$
Complejidad espacial en el peor de los casos	${\displaystyle O(n)}$total con auxiliar, auxiliar con listas enlazadas [1]${\displaystyle O(n)}$${\estilo de visualización O(1)}$

En informática , el ordenamiento por fusión (también conocido comúnmente como mergesort y merge-sort ^[2] ) es un algoritmo de ordenamiento eficiente, de propósito general y basado en comparaciones . La mayoría de las implementaciones producen un ordenamiento estable , lo que significa que el orden relativo de los elementos iguales es el mismo en la entrada y la salida. El ordenamiento por fusión es un algoritmo de divide y vencerás que fue inventado por John von Neumann en 1945. ^[3] Una descripción y un análisis detallados del ordenamiento por fusión de abajo a arriba aparecieron en un informe de Goldstine y von Neumann ya en 1948. ^[4]

Conceptualmente, una ordenación por combinación funciona de la siguiente manera:

1. Divida la lista desordenada en n sublistas, cada una de las cuales contiene un elemento (una lista de un elemento se considera ordenada).
2. Fusionar sublistas repetidamente para generar nuevas sublistas ordenadas hasta que solo quede una sublista. Esta será la lista ordenada.

Ejemplo de código similar a C que utiliza índices para un algoritmo de ordenación por fusión descendente que divide recursivamente la lista (llamada ejecuciones en este ejemplo) en sublistas hasta que el tamaño de la sublista sea 1, y luego fusiona esas sublistas para producir una lista ordenada. El paso de copia hacia atrás se evita alternando la dirección de la fusión con cada nivel de recursión (excepto una copia inicial única, que también se puede evitar).

Como ejemplo simple, considere una matriz con dos elementos. Los elementos se copian en B[] y luego se fusionan nuevamente en A[]. Si hay cuatro elementos, cuando se alcanza el nivel inferior del nivel de recursión, las ejecuciones de un solo elemento desde A[] se fusionan en B[] y luego, en el siguiente nivel superior de recursión, esas ejecuciones de dos elementos se fusionan en A[]. Este patrón continúa con cada nivel de recursión.

// La matriz A[] tiene los elementos a ordenar; la matriz B[] es una matriz de trabajo. void TopDownMergeSort ( A [], B [], n ) { CopyArray ( A , 0 , n , B ); // copia única de A[] a B[] TopDownSplitMerge ( A , 0 , n , B ); // ordenar datos de B[] en A[] }             // Dividir A[] en 2 ejecuciones, ordenar ambas ejecuciones en B[], fusionar ambas ejecuciones de B[] a A[] // iBegin es inclusivo; iEnd es exclusivo (A[iEnd] no está en el conjunto). void TopDownSplitMerge ( B [], iBegin , iEnd , A []) { if ( iEnd - iBegin <= 1 ) // si el tamaño de la ejecución == 1 return ; // considérelo ordenado // dividir la ejecución más larga de 1 elemento en mitades iMiddle = ( iEnd + iBegin ) / 2 ; // iMiddle = punto medio // ordenar recursivamente ambas ejecuciones de la matriz A[] en B[] TopDownSplitMerge ( A , iBegin , iMiddle , B ); // ordenar la ejecución izquierda TopDownSplitMerge ( A , iMiddle , iEnd , B ); // ordenar la ejecución correcta // fusionar las ejecuciones resultantes de la matriz B[] en A[] TopDownMerge ( B , iBegin , iMiddle , iEnd , A ); }                                       // La mitad izquierda de la fuente es A[iBegin:iMiddle-1]. // La mitad derecha de la fuente es A[iMiddle:iEnd-1]. // El resultado es B[iBegin:iEnd-1]. void TopDownMerge ( B [], iBegin , iMiddle , iEnd , A []) { i = iBegin , j = iMiddle ; // Mientras haya elementos en las ejecuciones izquierda o derecha... for ( k = iBegin ; k < iEnd ; k ++ ) { // Si existe la cabecera de la ejecución izquierda y es <= cabecera de la ejecución derecha existente. if ( i < iMiddle && ( j >= iEnd || A [ i ] <= A [ j ])) { B [ k ] = A [ i ]; i = i + 1 ; } else { B [ k ] = A [ j ]; j = j + 1 ; } } }                                                         void CopyArray ( A [], iBegin , iEnd , B []) { para ( k = iBegin ; k < iEnd ; k ++ ) B [ k ] = A [ k ]; }               

La ordenación de toda la matriz se logra mediante TopDownMergeSort(A, B, length(A)) .

Ejemplo de código similar a C que utiliza índices para un algoritmo de ordenamiento por fusión de abajo hacia arriba que trata la lista como una matriz de n sublistas (llamadas ejecuciones en este ejemplo) de tamaño 1 y fusiona iterativamente las sublistas de ida y vuelta entre dos búferes:

// la matriz A[] tiene los elementos a ordenar; la matriz B[] es una matriz de trabajo void BottomUpMergeSort ( A [], B [], n ) { // Cada ejecución de 1 elemento en A ya está "ordenada". // Realiza ejecuciones ordenadas sucesivamente más largas de longitud 2, 4, 8, 16... hasta que toda la matriz esté ordenada. for ( width = 1 ; width < n ; width = 2 * width ) { // La matriz A está llena de ejecuciones de longitud width. for ( i = 0 ; i < n ; i = i + 2 * width ) { // Fusionar dos ejecuciones: A[i:i+width-1] y A[i+width:i+2*width-1] en B[] // o copiar A[i:n-1] en B[] ( if (i+width >= n) ) BottomUpMerge ( A , i , min ( i + width , n ), min ( i + 2 * width , n ), B ); } // Ahora la matriz de trabajo B está llena de ejecuciones de longitud 2*width. // Copiar la matriz B a la matriz A para la siguiente iteración. // Una implementación más eficiente intercambiaría los roles de A y B. CopyArray ( B , A , n ); // Ahora la matriz A está llena de ejecuciones de longitud 2*width. } }                                                    // El tramo izquierdo es A[iLeft :iRight-1]. // El tramo derecho es A[iRight:iEnd-1]. void BottomUpMerge ( A [], iLeft , iRight , iEnd , B []) { i = iLeft , j = iRight ; // Mientras haya elementos en los tramos izquierdo o derecho... for ( k = iLeft ; k < iEnd ; k ++ ) { // Si existe un cabezal de tramo izquierdo y es <= existente un cabezal de tramo derecho. if ( i < iRight && ( j >= iEnd || A [ i ] <= A [ j ])) { B [ k ] = A [ i ]; i = i + 1 ; } else { B [ k ] = A [ j ]; j = j + 1 ; } } }                                                          vacío CopyArray ( B [], A [], n ) { para ( i = 0 ; i < n ; i ++ ) A [ i ] = B [ i ]; }              

Pseudocódigo para el algoritmo de ordenamiento por fusión de arriba hacia abajo que divide recursivamente la lista de entrada en sublistas más pequeñas hasta que las sublistas se ordenan de manera trivial y luego fusiona las sublistas mientras regresa a la cadena de llamadas.

función merge_sort( lista m) es // Caso base. Por definición, se ordena una lista de cero o un elemento.  Si la longitud de m ≤ 1, se  devuelve m // Caso recursivo. Primero, divida la lista en sublistas de igual tamaño // que consten de la primera mitad y la segunda mitad de la lista. // Esto supone que las listas comienzan en el índice 0.  var left := lista vacía var right := lista vacía para cada x con índice i en m do  if i < (length of m)/2 then añadir x a la izquierda demás añade x a la derecha // Ordena recursivamente ambas sublistas. izquierda := merge_sort(izquierda) derecha := merge_sort(derecha) // Luego fusiona las sublistas ahora ordenadas. devolver fusionar(izquierda, derecha)

En este ejemplo, la función de fusión fusiona las sublistas izquierda y derecha.

La función merge(left, right) es  var resultado:= lista vacía mientras que la izquierda no esté vacía y la derecha no esté vacía, haga  si primero(izquierda) ≤ primero(derecha) entonces añadir primero (izquierda) al resultado izquierda := resto(izquierda) demás añadir primero (derecha) al resultado derecha := resto(derecha) // Tanto la izquierda como la derecha pueden tener elementos restantes; consumirlos. // (En realidad, solo se ingresará a uno de los siguientes bucles).  mientras la izquierda no esté vacía, haga añadir primero (izquierda) al resultado izquierda := resto(izquierda) mientras que la derecha no esté vacía añadir primero (derecha) al resultado derecha := resto(derecha) devolver resultado

Pseudocódigo para el algoritmo de ordenación por fusión ascendente que utiliza una pequeña matriz de tamaño fijo de referencias a nodos, donde array[i] es una referencia a una lista de tamaño 2 ⁱ o nil . node es una referencia o puntero a un nodo. La función merge() sería similar a la que se muestra en el ejemplo de listas de fusión descendentes, fusiona dos listas ya ordenadas y maneja listas vacías. En este caso, merge() utilizaría node para sus parámetros de entrada y valor de retorno.

La función merge_sort( nodo cabeza) es // retorna si la lista esta vacia si head = nil entonces  retorna nil var  nodo array[32]; inicialmente todos nil var  nodo resultado var  nodo siguiente var  int i resultado := cabeza // fusionar nodos en una matriz mientras resultado ≠ nulo hacer siguiente := resultado.siguiente; resultado.siguiente := nil para (i = 0; (i < 32) && (array[i] ≠ nulo); i += 1) hacer resultado := fusionar(matriz[i], resultado) matriz[i] := nulo // no pases del final de la matriz si i = 32 entonces yo -= 1 matriz[i] := resultado resultado := siguiente // fusionar matriz en una sola lista resultado := nulo para (i = 0; i < 32; i += 1) hacer resultado := fusionar(matriz[i], resultado) devolver resultado

Pseudocódigo similar a Haskell , que muestra cómo se puede implementar la ordenación por fusión en dicho lenguaje utilizando construcciones e ideas de programación funcional .

ordenación_fusión :: [ a ] ​​-> [ a ] ​​ordenación_fusión ( [] ) = [] ordenación_fusión ([ x ]) = [ x ] ordenación_fusión ( xs ) = unir ( ordenación_fusión ( izquierda ), ordenación_fusión ( derecha )) donde ( izquierda , derecha ) = dividir ( xs , longitud ( xs ) / 2 ) unir :: ([ a ], [ a ]) -> [ a ] ​​unir ( [] , xs ) = xs unir ( xs , [] ) = xs unir ( x : xs , y : ys ) | si x ≤ y = x : unir ( xs , y : ys ) | de lo contrario = y : unir ( x : xs , ys )                                                          

Al ordenar n objetos, el ordenamiento por fusión tiene un rendimiento promedio y en el peor de los casos de O ( n  log  n ) comparaciones. Si el tiempo de ejecución (número de comparaciones) del ordenamiento por fusión para una lista de longitud n es T ( n ), entonces la relación de recurrencia T ( n ) = 2 T ( n /2) + n se desprende de la definición del algoritmo (aplicar el algoritmo a dos listas de la mitad del tamaño de la lista original y sumar los n pasos dados para fusionar las dos listas resultantes). ^[5] La forma cerrada se desprende del teorema maestro para recurrencias de divide y vencerás .

La cantidad de comparaciones realizadas por ordenación por combinación en el peor de los casos se da mediante los números de ordenación . Estos números son iguales o ligeramente menores que ( n  ⌈ lg  n ⌉ − 2 ^{⌈lg  n ⌉} + 1), que está entre ( n  lg  n − n + 1) y ( n  lg  n + n + O(lg  n )). ^[6] El mejor caso de la ordenación por combinación requiere aproximadamente la mitad de iteraciones que su peor caso. ^[7]

Para un valor n grande y una lista de entrada ordenada aleatoriamente, el número esperado (promedio) de comparaciones de la ordenación por combinación se aproxima a α · n menos que el peor caso, donde${\displaystyle \alpha =-1+\sum _{k=0}^{\infty }{\frac {1}{2^{k}+1}}\aproximadamente 0,2645.}$

En el peor de los casos, la ordenación por combinación utiliza aproximadamente un 39% menos de comparaciones que la ordenación rápida en su caso promedio , y en términos de movimientos, la complejidad del peor caso de la ordenación por combinación es O ( n  log  n ), la misma complejidad que el mejor caso de la ordenación rápida. ^[7]

La ordenación por combinación es más eficiente que la ordenación rápida para algunos tipos de listas si los datos que se van a ordenar solo se pueden acceder de manera eficiente de manera secuencial, y por eso es popular en lenguajes como Lisp , donde las estructuras de datos a las que se accede de manera secuencial son muy comunes. A diferencia de algunas implementaciones (eficientes) de la ordenación rápida, la ordenación por combinación es una ordenación estable.

La implementación más común de la ordenación por combinación no ordena en el lugar; ^[8] por lo tanto, el tamaño de la memoria de la entrada debe asignarse para que se almacene la salida ordenada (vea a continuación las variaciones que necesitan solo n /2 espacios adicionales).

Un ordenamiento por fusión natural es similar a un ordenamiento por fusión ascendente, excepto que se aprovechan todas las ejecuciones que ocurren naturalmente (secuencias ordenadas) en la entrada. Se pueden aprovechar tanto las ejecuciones monótonas como las bitónicas (que alternan arriba/abajo), siendo las listas (o equivalentemente cintas o archivos) estructuras de datos convenientes (usadas como colas FIFO o pilas LIFO ). ^[9] En el ordenamiento por fusión ascendente, el punto de partida supone que cada ejecución tiene un elemento de longitud. En la práctica, los datos de entrada aleatorios tendrán muchas ejecuciones cortas que simplemente están ordenadas. En el caso típico, el ordenamiento por fusión natural puede no necesitar tantos pases porque hay menos ejecuciones para fusionar. En el mejor de los casos, la entrada ya está ordenada (es decir, es una ejecución), por lo que el ordenamiento por fusión natural solo necesita hacer un pase a través de los datos. En muchos casos prácticos, hay ejecuciones naturales largas y, por esa razón, el ordenamiento por fusión natural se aprovecha como el componente clave de Timsort . Ejemplo:

Inicio: 3 4 2 1 7 5 8 9 0 6Seleccione carreras: (3 4)(2)(1 7)(5 8 9)(0 6)Fusionar: (2 3 4)(1 5 7 8 9)(0 6)Fusionar: (1 2 3 4 5 7 8 9)(0 6)Fusionar: (0 1 2 3 4 5 6 7 8 9)

Formalmente, se dice que la ordenación por fusión natural es óptima en cuanto a ejecuciones, donde es el número de ejecuciones en , menos uno.${\displaystyle {\mathtt {Corre}}(L)}$${\estilo de visualización L}$

Los ordenamientos de selección de reemplazo de torneo se utilizan para recopilar las ejecuciones iniciales para algoritmos de ordenamiento externos.

En lugar de fusionar dos bloques a la vez, una fusión ping-pong fusiona cuatro bloques a la vez. Los cuatro bloques ordenados se fusionan simultáneamente en el espacio auxiliar en dos bloques ordenados, luego los dos bloques ordenados se fusionan nuevamente en la memoria principal. Al hacerlo, se omite la operación de copia y se reduce el número total de movimientos a la mitad. Una implementación temprana de dominio público de una fusión de cuatro a la vez fue realizada por WikiSort en 2014, el método se describió más tarde ese año como una optimización para la clasificación de paciencia y se denominó fusión ping-pong. ^{[10] [11]} Quadsort implementó el método en 2020 y lo denominó fusión cuádruple. ^[12]

Una desventaja de la ordenación por fusión, cuando se implementa en matrices, es que requiere una memoria de trabajo de O ( n ) . Se han sugerido varios métodos para reducir la memoria o hacer que la ordenación por fusión se realice completamente en el lugar :

• Kronrod (1969) sugirió una versión alternativa de la ordenación por fusión que utiliza espacio adicional constante.
• Katajainen et al. presentan un algoritmo que requiere una cantidad constante de memoria de trabajo: suficiente espacio de almacenamiento para albergar un elemento de la matriz de entrada y espacio adicional para albergar O (1) punteros en la matriz de entrada. Logran un límite de tiempo de O ( n log n ) con constantes pequeñas, pero su algoritmo no es estable. ^[13]
• Se han hecho varios intentos para producir un algoritmo de fusión in situ que se pueda combinar con un ordenamiento por fusión estándar (de arriba hacia abajo o de abajo hacia arriba) para producir un ordenamiento por fusión in situ. En este caso, la noción de "in situ" se puede relajar para significar "tomar espacio de pila logarítmico", porque el ordenamiento por fusión estándar requiere esa cantidad de espacio para su propio uso de pila. Geffert et al. demostraron que la fusión estable in situ es posible en tiempo O ( n log n ) utilizando una cantidad constante de espacio de borrador, pero su algoritmo es complicado y tiene factores constantes altos: la fusión de matrices de longitud n y m puede tomar 5 n + 12 m + o ( m ) movimientos. ^[14] Este alto factor constante y complicado algoritmo in situ se hizo más simple y fácil de entender. Bing-Chao Huang y Michael A. Langston ^[15] presentaron un algoritmo de tiempo lineal sencillo y práctico de fusión in situ para fusionar una lista ordenada utilizando una cantidad fija de espacio adicional. Ambos han utilizado el trabajo de Kronrod y otros. Se fusiona en tiempo lineal y espacio extra constante. El algoritmo toma un poco más de tiempo promedio que los algoritmos de ordenamiento por fusión estándar, libres de explotar O(n) celdas de memoria extra temporales, por menos de un factor de dos. Aunque el algoritmo es mucho más rápido en la práctica, también es inestable para algunas listas. Pero usando conceptos similares, han podido resolver este problema. Otros algoritmos in situ incluyen SymMerge, que toma O (( n + m ) log ( n + m )) tiempo en total y es estable. ^[16] Conectar un algoritmo de este tipo al ordenamiento por fusión aumenta su complejidad al no linealítmico , pero aún cuasilineal , O ( n (log n ) ² ) .
• Muchas aplicaciones de ordenamiento externo utilizan una forma de ordenamiento por fusión donde la entrada se divide en una cantidad mayor de sublistas, idealmente en una cantidad tal que al fusionarlas aún quepa en la memoria principal el conjunto de páginas actualmente procesadas .
• Una variante moderna, estable, lineal y de fusión en el lugar es la ordenación por fusión en bloque , que crea una sección de valores únicos para usar como espacio de intercambio.
• La sobrecarga espacial se puede reducir a sqrt( n ) mediante búsquedas binarias y rotaciones. ^[17] Este método lo emplean la biblioteca STL de C++ y quadsort. ^[12]
• Una alternativa para reducir la copia en múltiples listas es asociar un nuevo campo de información con cada clave (los elementos en m se denominan claves). Este campo se utilizará para vincular las claves y cualquier información asociada en una lista ordenada (una clave y su información relacionada se denominan registro). Luego, la fusión de las listas ordenadas se lleva a cabo modificando los valores de los vínculos; no es necesario mover ningún registro. Un campo que contiene solo un vínculo generalmente será más pequeño que un registro completo, por lo que también se utilizará menos espacio. Esta es una técnica de ordenación estándar, no restringida a la ordenación por fusión.
• Una forma sencilla de reducir la sobrecarga de espacio a n /2 es mantener left y right como una estructura combinada, copiar solo la parte izquierda de m en el espacio temporal y dirigir la rutina de fusión para colocar la salida fusionada en m . Con esta versión, es mejor asignar el espacio temporal fuera de la rutina de fusión , de modo que solo se necesite una asignación. La copia excesiva mencionada anteriormente también se mitiga, ya que el último par de líneas antes de la declaración de resultado de retorno (función merge en el pseudocódigo anterior) se vuelve superflua.

Una ordenación por fusión externa es práctica de ejecutar utilizando unidades de disco o cinta cuando los datos que se van a ordenar son demasiado grandes para caber en la memoria . La ordenación externa explica cómo se implementa la ordenación por fusión con unidades de disco. Una ordenación típica con unidad de cinta utiliza cuatro unidades de cinta. Toda la E/S es secuencial (excepto los rebobinados al final de cada pasada). Una implementación mínima puede funcionar con solo dos búferes de registro y algunas variables de programa.

Al nombrar las cuatro unidades de cinta como A, B, C, D, con los datos originales en A y utilizando solo dos búferes de registro, el algoritmo es similar a la implementación ascendente, utilizando pares de unidades de cinta en lugar de matrices en la memoria. El algoritmo básico se puede describir de la siguiente manera:

1. Fusionar pares de registros de A; escribir sublistas de dos registros alternativamente en C y D.
2. Fusionar sublistas de dos registros de C y D en sublistas de cuatro registros; escribiéndolas alternativamente en A y B.
3. Fusionar sublistas de cuatro registros de A y B en sublistas de ocho registros; escribirlas alternativamente en C y D
4. Repita hasta que tenga una lista que contenga todos los datos, ordenados en logaritmo ₂ ( n ) pasadas.

En lugar de comenzar con ejecuciones muy cortas, generalmente se utiliza un algoritmo híbrido , donde el paso inicial leerá muchos registros en la memoria, realizará una clasificación interna para crear una ejecución larga y luego distribuirá esas ejecuciones largas en el conjunto de salida. El paso evita muchos pasos iniciales. Por ejemplo, una clasificación interna de 1024 registros ahorrará nueve pasos. La clasificación interna suele ser grande porque tiene ese beneficio. De hecho, existen técnicas que pueden hacer que las ejecuciones iniciales sean más largas que la memoria interna disponible. Una de ellas, el 'snowplow' de Knuth (basado en un min-heap binario ), genera ejecuciones dos veces más largas (en promedio) que el tamaño de la memoria utilizada. ^[18]

Con un poco de sobrecarga, el algoritmo anterior se puede modificar para utilizar tres cintas. También se puede lograr un tiempo de ejecución de O ( n log n ) utilizando dos colas , o una pila y una cola, o tres pilas. En la otra dirección, utilizando k > dos cintas (y O ( k ) elementos en la memoria), podemos reducir la cantidad de operaciones de cinta en O (log k ) veces utilizando una fusión de k/2 vías .

Una ordenación por fusión más sofisticada que optimiza el uso de la unidad de cinta (y disco) es la ordenación por fusión polifásica .

En las computadoras modernas, la localidad de referencia puede ser de suma importancia en la optimización del software , porque se utilizan jerarquías de memoria de múltiples niveles. Se han propuesto versiones del algoritmo de ordenación por fusión que tienen en cuenta la memoria caché , cuyas operaciones se han elegido específicamente para minimizar el movimiento de páginas dentro y fuera de la memoria caché de una máquina. Por ejemplo, el algoritmoEl algoritmo de ordenación por fusión en mosaico detiene la partición de submatrices cuando se alcanzan submatrices de tamaño S, donde S es la cantidad de elementos de datos que caben en la memoria caché de una CPU. Cada una de estas submatrices se ordena con un algoritmo de ordenación en el lugar, comola ordenación por inserción, para desalentar los intercambios de memoria, y luego se completa la ordenación por fusión normal de la manera recursiva estándar. Este algoritmo ha demostrado un mejor rendimiento^{[ se necesita un ejemplo ]}en máquinas que se benefician de la optimización de la memoria caché. (LaMarca y Ladner 1997)

El algoritmo de ordenación por fusión se paraleliza bien gracias al uso del método de dividir y vencer . A lo largo de los años se han desarrollado varias variantes paralelas del algoritmo. Algunos algoritmos de ordenación por fusión paralelos están estrechamente relacionados con el algoritmo de fusión descendente secuencial, mientras que otros tienen una estructura general diferente y utilizan el método de fusión de K vías .

El procedimiento de ordenación por fusión secuencial se puede describir en dos fases: la fase de división y la fase de fusión. La primera consiste en muchas llamadas recursivas que realizan repetidamente el mismo proceso de división hasta que las subsecuencias se ordenan de manera trivial (conteniendo un elemento o ningún elemento). Un enfoque intuitivo es la paralelización de esas llamadas recursivas. ^[19] El siguiente pseudocódigo describe la ordenación por fusión con recursión paralela utilizando las palabras clave fork y join :

// Ordena los elementos lo a hi (exclusivos) de la matriz A. El algoritmo mergesort(A, lo, hi) es  si lo+1 < hi entonces // Dos o más elementos. medio := ⌊(bajo + alto) / 2⌋ bifurcación mergesort(A, lo, mid) mergesort(A, medio, alto) unirse fusionar(A, bajo, medio, alto)

Este algoritmo es una modificación trivial de la versión secuencial y no se paraleliza bien. Por lo tanto, su aceleración no es muy impresionante. Tiene un lapso de , que es solo una mejora de en comparación con la versión secuencial (consulte Introducción a los algoritmos ). Esto se debe principalmente al método de fusión secuencial, ya que es el cuello de botella de las ejecuciones paralelas.${\displaystyle \Theta (n)}$${\displaystyle \Theta (\log n)}$

Se puede lograr un mejor paralelismo utilizando un algoritmo de fusión paralela . Cormen et al. presentan una variante binaria que fusiona dos subsecuencias ordenadas en una secuencia de salida ordenada. ^[19]

En una de las secuencias (la más larga si no tienen la misma longitud) se selecciona el elemento del índice medio. Su posición en la otra secuencia se determina de tal manera que esta secuencia permanecería ordenada si este elemento se insertara en esa posición. De esta manera, se sabe cuántos otros elementos de ambas secuencias son más pequeños y se puede calcular la posición del elemento seleccionado en la secuencia de salida. Para las secuencias parciales de los elementos más pequeños y más grandes creadas de esta manera, el algoritmo de fusión se ejecuta nuevamente en paralelo hasta que se alcanza el caso base de la recursión.

El siguiente pseudocódigo muestra el método de ordenamiento por fusión paralela modificado utilizando el algoritmo de fusión paralela (adoptado de Cormen et al.).

/** * A: Matriz de entrada * B: Matriz de salida * lo: límite inferior * hola: límite superior * off: desplazamiento */El algoritmo parallelMergesort(A, lo, hi, B, off) es len := hola - lo + 1 Si len == 1 entonces B[apagado] := A[bajo] De lo contrario, sea T[1..len] una nueva matriz medio := ⌊(bajo + alto) / 2⌋ medio' := medio - bajo + 1 bifurcación paralelaMergesort(A, lo, mid, T, 1) paraleloMergesort(A, medio + 1, alto, T, medio' + 1) unirse  paraleloMerge(T, 1, mid', mid' + 1, len, B, off)

Para analizar una relación de recurrencia para el peor caso, las llamadas recursivas de parallelMergesort deben incorporarse solo una vez debido a su ejecución paralela, obteniendo

$${\displaystyle T_{\infty }^{\text{ordenar}}(n)=T_{\infty }^{\text{ordenar}}\left({\frac {n}{2}}\right)+T_{\infty }^{\text{combinar}}(n)=T_{\infty }^{\text{ordenar}}\left({\frac {n}{2}}\right)+\Theta \left(\log(n)^{2}\right).}$$

Para obtener información detallada sobre la complejidad del procedimiento de fusión paralela, consulte Algoritmo de fusión .

La solución de esta recurrencia viene dada por

$${\displaystyle T_{\infty }^{\text{ordenación}}=\Theta \left(\log(n)^{3}\right).}$$

Este algoritmo de fusión paralela alcanza un paralelismo de , que es mucho mayor que el paralelismo del algoritmo anterior. Este tipo de ordenamiento puede funcionar bien en la práctica cuando se combina con un ordenamiento secuencial estable y rápido, como el ordenamiento por inserción , y una fusión secuencial rápida como caso base para fusionar matrices pequeñas. ^[20]${\textstyle \Theta \left({\frac {n}{(\log n)^{2}}}\right)}$

Parece arbitrario restringir los algoritmos de ordenamiento por fusión a un método de fusión binaria, ya que normalmente hay p > 2 procesadores disponibles. Un mejor enfoque puede ser utilizar un método de fusión de K vías , una generalización de la fusión binaria, en el que se fusionan las secuencias ordenadas. Esta variante de fusión es muy adecuada para describir un algoritmo de ordenamiento en una PRAM . ^{[21] [22]}${\estilo de visualización k}$

Dada una secuencia de elementos no ordenados, el objetivo es ordenar la secuencia con los procesadores disponibles . Estos elementos se distribuyen equitativamente entre todos los procesadores y se ordenan localmente utilizando un algoritmo de ordenamiento secuencial . Por lo tanto, la secuencia consta de secuencias ordenadas de longitud . Para simplificar, sea un múltiplo de , de modo que para .${\estilo de visualización n}$${\estilo de visualización p}$${\displaystyle S_{1},...,S_{p}}$${\textstyle \lceil {\frac {n}{p}}\rceil }$${\estilo de visualización n}$${\estilo de visualización p}$${\textstyle \left\vert S_{i}\right\vert ={\frac {n}{p}}}$${\displaystyle i=1,...,p}$

Estas secuencias se utilizarán para realizar una selección multisecuencial/selección divisoria. Para , el algoritmo determina elementos divisores con rango global . Luego, las posiciones correspondientes de en cada secuencia se determinan con búsqueda binaria y, por lo tanto, se dividen en subsecuencias con .${\displaystyle j=1,...,p}$${\displaystyle v_{j}}$${\textstyle k=j{\frac {n}{p}}}$${\displaystyle v_{1},...,v_{p}}$$Estilo de visualización S_{i}}$$Estilo de visualización S_{i}}$${\estilo de visualización p}$${\displaystyle S_{i,1},...,S_{i,p}}$${\textstyle S_{i,j}:=\{x\in S_{i}|rango(v_{j-1})<rango(x)\leq rango(v_{j})\}}$

Además, los elementos de se asignan al procesador , es decir, todos los elementos entre rango y rango , que se distribuyen entre todos los . Por lo tanto, cada procesador recibe una secuencia de secuencias ordenadas. El hecho de que el rango de los elementos del divisor se haya elegido globalmente proporciona dos propiedades importantes: por un lado, se ha elegido de forma que cada procesador pueda seguir operando con los elementos después de la asignación. El algoritmo está perfectamente equilibrado en cuanto a la carga . Por otro lado, todos los elementos del procesador son menores o iguales que todos los elementos del procesador . Por lo tanto, cada procesador realiza la fusión de p -way localmente y, por lo tanto, obtiene una secuencia ordenada a partir de sus subsecuencias. Debido a la segunda propiedad, no es necesario realizar ninguna fusión de p -way adicional, los resultados solo se tienen que juntar en el orden del número de procesador.${\displaystyle S_{1,i},...,S_{p,i}}$${\estilo de visualización i}$${\textstyle (i-1){\frac {n}{p}}}$${\textstyle i{\frac {n}{p}}}$$Estilo de visualización S_{i}}$${\estilo de visualización k}$$estilo de visualización v_{i}}$${\estilo de visualización k}$${\textstyle n/p}$${\estilo de visualización i}$${\estilo de visualización i+1}$

En su forma más simple, dadas secuencias ordenadas distribuidas uniformemente en procesadores y un rango , la tarea es encontrar un elemento con un rango global en la unión de las secuencias. Por lo tanto, esto se puede utilizar para dividir cada una en dos partes en un índice divisor , donde la parte inferior contiene solo elementos que son más pequeños que , mientras que los elementos más grandes que se encuentran en la parte superior.${\estilo de visualización p}$${\displaystyle S_{1},...,S_{p}}$${\estilo de visualización p}$${\estilo de visualización k}$${\estilo de visualización x}$${\estilo de visualización k}$$Estilo de visualización S_{i}}$$estilo de visualización l_{i}}$${\estilo de visualización x}$${\estilo de visualización x}$

El algoritmo secuencial presentado devuelve los índices de las divisiones en cada secuencia, por ejemplo, los índices en secuencias tales que tienen un rango global menor que y . ^[23]$estilo de visualización l_{i}}$$Estilo de visualización S_{i}}$${\displaystyle S_{i}[l_{i}]}$${\estilo de visualización k}$${\displaystyle \mathrm {rango} \left(S_{i}[l_{i}+1]\right)\geq k}$

El algoritmo msSelect(S: Matriz de secuencias ordenadas [ S_1,..,S_p], k: int) es  para i = 1 a p (i_i, r_i) = (0, |i_i|-1) mientras exista i: l_i < r_i hacer// elige el elemento pivote en S_j[l_j], .., S_j[r_j], elige j aleatorio de manera uniformev := pickPivot(S, l, r)para i = 1 a p hacer  m_i = binarySearch(v, S_i[l_i, r_i]) // secuencialmentesi m_1 + ... + m_p >= k entonces // m_1+ ... + m_p es el rango global de v r := m // asignación vectorialdemás yo:= yo volver l

Para el análisis de complejidad se elige el modelo PRAM . Si los datos se distribuyen uniformemente en todos los , la ejecución p-fold del método binarySearch tiene un tiempo de ejecución de . La profundidad de recursión esperada es como en el Quickselect ordinario . Por lo tanto, el tiempo de ejecución general esperado es .${\estilo de visualización p}$${\displaystyle {\mathcal {O}}\left(p\log \left(n/p\right)\right)}$${\displaystyle {\mathcal {O}}(\log \left(\textstyle \sum _{i}|S_{i}|\right)\right)={\mathcal {O}}(\log(n))}$${\displaystyle {\mathcal {O}}\left(p\log(n/p)\log(n)\right)}$

Este algoritmo, que se aplica en la ordenación por fusión de múltiples vías paralelas, se debe invocar en paralelo de modo que todos los elementos divisores de rango para se encuentren simultáneamente. Estos elementos divisores se pueden utilizar para dividir cada secuencia en partes, con el mismo tiempo de ejecución total de .${\textstyle i{\frac {n}{p}}}$${\displaystyle i=1,..,p}$${\estilo de visualización p}$${\displaystyle {\mathcal {O}}\left(p\,\log(n/p)\log(n)\right)}$

A continuación se presenta el pseudocódigo completo del algoritmo de ordenamiento por fusión multidireccional en paralelo. Suponemos que existe una sincronización de barrera antes y después de la selección de secuencias múltiples, de modo que cada procesador pueda determinar los elementos de división y la partición de secuencias correctamente.

/** * d: Matriz de elementos no ordenados * n: Número de elementos * p: Número de procesadores * devuelve una matriz ordenada */algoritmo parallelMultiwayMergesort(d : Array, n : int, p : int) es o := new Array[0, n] // la matriz de salida para i = 1 a p hacer en paralelo // cada procesador en paralelo S_i := d[(i-1) * n/p, i * n/p] // Secuencia de longitud n/psort(S_i) // ordenar localmente sincronizarv_i := msSelect([S_1,...,S_p], i * n/p) // elemento con rango global i * n/p sincronizar(S_i,1, ..., S_i,p) := sequence_partitioning(si, v_1, ..., v_p) // divide s_i en subsecuencias o[(i-1) * n/p, i * n/p] := kWayMerge(s_1,i, ..., s_p,i) // fusionar y asignar a la matriz de salida volver o

En primer lugar, cada procesador ordena los elementos asignados localmente utilizando un algoritmo de ordenación con una complejidad de . Después de eso, los elementos divisores deben calcularse en tiempo . Finalmente, cada grupo de divisiones debe fusionarse en paralelo por cada procesador con un tiempo de ejecución de utilizando un algoritmo de fusión secuencial de p-way . Por lo tanto, el tiempo de ejecución total viene dado por${\estilo de visualización n/p}$${\displaystyle {\mathcal {O}}\left(n/p\;\log(n/p)\right)}$${\displaystyle {\mathcal {O}}\left(p\,\log(n/p)\log(n)\right)}$${\estilo de visualización p}$${\displaystyle {\mathcal {O}}(\log(p)\;n/p)}$

${\displaystyle {\mathcal {O}}({\frac {n}{p}}\log \left({\frac {n}{p}}\right)+p\log \left({\frac {n}{p}}\right)\log(n)+{\frac {n}{p}}\log(p)\right)}$.

El algoritmo de ordenación por fusión de múltiples vías es muy escalable gracias a su alta capacidad de paralelización, que permite el uso de muchos procesadores. Esto hace que el algoritmo sea un candidato viable para ordenar grandes cantidades de datos, como los que se procesan en clústeres de computadoras . Además, dado que en tales sistemas la memoria no suele ser un recurso limitante, la desventaja de la complejidad espacial de la ordenación por fusión es insignificante. Sin embargo, otros factores se vuelven importantes en tales sistemas, que no se tienen en cuenta al modelar en una PRAM . Aquí, se deben considerar los siguientes aspectos: la jerarquía de memoria , cuando los datos no caben en la caché de los procesadores, o la sobrecarga de comunicación del intercambio de datos entre procesadores, que podría convertirse en un cuello de botella cuando ya no se puede acceder a los datos a través de la memoria compartida.

Sanders et al. han presentado en su artículo un algoritmo paralelo sincrónico masivo para la ordenación por fusión multinivel y multidireccional, que divide los procesadores en grupos de tamaño . Todos los procesadores ordenan localmente primero. A diferencia de la ordenación por fusión multidireccional de un solo nivel, estas secuencias se dividen luego en partes y se asignan a los grupos de procesadores apropiados. Estos pasos se repiten recursivamente en esos grupos. Esto reduce la comunicación y, especialmente, evita problemas con muchos mensajes pequeños. La estructura jerárquica de la red real subyacente se puede utilizar para definir los grupos de procesadores (por ejemplo, bastidores , clústeres , ...). ^[22]${\estilo de visualización p}$${\estilo de visualización r}$${\estilo de visualización p'}$${\estilo de visualización r}$

El ordenamiento por fusión fue uno de los primeros algoritmos de ordenamiento en los que se logró una velocidad óptima, con Richard Cole utilizando un algoritmo de submuestreo inteligente para asegurar una fusión O (1). ^[24] Otros algoritmos de ordenamiento paralelo sofisticados pueden lograr los mismos límites de tiempo o mejores con una constante menor. Por ejemplo, en 1991 David Powers describió un ordenamiento rápido paralelizado (y un ordenamiento por radix relacionado ) que puede operar en tiempo O (log n ) en una máquina de acceso aleatorio paralelo (PRAM) CRCW con n procesadores realizando particiones de manera implícita. ^{[25] Powers demuestra además que una versión segmentada del ordenamiento por} fusión bitónica de Batcher en tiempo O ((log n ) ² ) en una red de ordenamiento mariposa es en la práctica realmente más rápida que sus ordenamientos O (log n ) en una PRAM, y proporciona una discusión detallada de las sobrecargas ocultas en comparación, el ordenamiento por radix y paralelo. ^[26]

Aunque el heapsort tiene los mismos límites de tiempo que el merge sort, requiere solo Θ(1) espacio auxiliar en lugar del Θ( n ) del merge sort. En arquitecturas modernas típicas, las implementaciones eficientes de quicksort generalmente superan al merge sort para ordenar arreglos basados ​​en RAM. ^[27] Los quicksorts son preferidos cuando el tamaño de los datos a ordenar es menor, ya que la complejidad espacial para quicksort es O(log n ), ayuda a utilizar la localidad de caché mejor que el merge sort (con complejidad espacial O(n)). ^[27] Por otro lado, el merge sort es un ordenamiento estable y es más eficiente en el manejo de medios secuenciales de acceso lento. El merge sort es a menudo la mejor opción para ordenar una lista enlazada : en esta situación es relativamente fácil implementar un merge sort de tal manera que requiera solo Θ(1) espacio extra, y el lento desempeño de acceso aleatorio de una lista enlazada hace que algunos otros algoritmos (como quicksort) tengan un desempeño deficiente, y otros (como heapsort) completamente imposibles.

A partir de Perl 5.8, el ordenamiento por fusión es su algoritmo de ordenamiento predeterminado (en versiones anteriores de Perl era quicksort). ^[28] En Java , los métodos Arrays.sort() utilizan el ordenamiento por fusión o un quicksort ajustado según los tipos de datos y, para una implementación más eficiente, cambian al ordenamiento por inserción cuando se ordenan menos de siete elementos de matriz. ^[29] El núcleo Linux utiliza el ordenamiento por fusión para sus listas enlazadas. ^[30]

Timsort , un híbrido optimizado de ordenación por fusión y ordenación por inserción, se utiliza en una variedad de plataformas de software y lenguajes, incluidas las plataformas Java y Android ^{[31] y} Python lo utiliza desde la versión 2.3; desde la versión 3.11, la política de fusión de Timsort se actualizó a Powersort. ^[32]

• Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L .; Stein, Clifford (2009) [1990]. Introducción a los algoritmos (3ª ed.). MIT Press y McGraw-Hill. ISBN 0-262-03384-4.
• Katajainen, Jyrki; Pasanen, Tomi; Teuhola, Jukka (1996). "Practical in-place mergesort". Nordic Journal of Computing . 3 (1): 27–40. CiteSeerX  10.1.1.22.8523 . ISSN  1236-6064. Archivado desde el original el 2011-08-07 . Consultado el 2009-04-04 .. También es práctica la ordenación por fusión in situ. También [3]
• Knuth, Donald (1998). "Sección 5.2.4: Ordenación por fusión". Ordenación y búsqueda . El arte de la programación informática . Vol. 3 (2.ª ed.). Addison-Wesley. págs. 158–168. ISBN 0-201-89685-0.
• Kronrod, MA (1969). "Algoritmo de ordenamiento óptimo sin campo operacional". Matemáticas soviéticas - Doklady . 10 : 744.
• LaMarca, A.; Ladner, RE (1997). "La influencia de las cachés en el rendimiento de la ordenación". Proc. 8.° Congreso Anual de ACM-SIAM sobre Algoritmos Discretos (SODA97) : 370–379. CiteSeerX  10.1.1.31.1153 .
• Skiena, Steven S. (2008). "4.5: Mergesort: Ordenación por división y conquista". Manual de diseño de algoritmos (2.ª ed.). Springer. pp. 120–125. ISBN 978-1-84800-069-8.
• Sun Microsystems. "Arrays API (Java SE 6)" (API de matrices (Java SE 6)) . Consultado el 19 de noviembre de 2007 .
• Oracle Corp. "Arrays (Java SE 10 & JDK 10)" (Matrices (Java SE 10 y JDK 10)) . Consultado el 23 de julio de 2018 .

La implementación del algoritmo de Wikibook tiene una página sobre el tema: Ordenamiento por fusión

• Algoritmos de ordenamiento animados: ordenamiento por combinación en Wayback Machine (archivado el 6 de marzo de 2015): demostración gráfica
• Estructuras de datos abiertas - Sección 11.1.1 - Ordenación por combinación, Pat Morin