Ordenación por fusión

El algoritmo de ordenación por fusión (también escrito comúnmente como mergesort o merge-sort ^{[ 2 ]} ) es un algoritmo de ordenación eficiente, de propósito general y basado en comparaciones . La mayoría de las implementaciones de este algoritmo son estables , lo que significa que el orden relativo de los elementos iguales se mantiene entre la entrada y la salida. La ordenación por fusión es un algoritmo de divide y vencerás inventado por John von Neumann en 1945. ^{[ 3 ]} Una descripción y análisis detallados de la ordenación por fusión ascendente aparecieron en un informe de Goldstine y von Neumann ya en 1948. ^{[ 4 ]}

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

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

El algoritmo de ordenación por fusión es eficiente porque la fusión y la ordenación de dos sublistas se pueden realizar en tiempo lineal, siempre que las sublistas ya estén ordenadas.

// Copia una sección del array a en el array b (desde begin hasta end - 1) void copyArray ( int [] a , int begin , int end , int [] b ) { for ( int k = begin ; k < end ; ++ k ) { b [ k ] = a [ k ] ; } }// Fusiona dos mitades ordenadas (de a) en una única secuencia ordenada (en b) void topDownMerge ( int [] a , int begin , int middle , int end , int [] b ) { int i = begin ; int j = middle ;// Fusionar las dos secuencias ordenadas en b para ( int k = begin ; k < end ; ++ k ) { if ( i < middle && ( j >= end || a [ i ] <= a [ j ] )) { b [ k ] = a [ i ] ; // Tomar el elemento de la secuencia izquierda i ++ ; } else { b [ k ] = a [ j ] ; // Tomar el elemento de la secuencia derecha j ++ ; } } }// Divide el array a en dos mitades, ordena ambas mitades en b, // y fusiona las mitades ordenadas de nuevo en a void topDownSplitMerge ( int [] a , int begin , int end , int [] b ) { if ( end - begin <= 1 ) { return ; // Caso base: El tamaño de ejecución es 1, por lo que ya está ordenado }int medio = ( inicio + fin ) / 2 ; // Encuentra el punto medio para dividir el array// Ordena recursivamente las mitades izquierda y derecha en b topDownSplitMerge ( b , begin , middle , a ); topDownSplitMerge ( b , middle , end , a );// Fusiona las mitades ordenadas de nuevo en un topDownMerge ( b , begin , middle , end , a ); }void topDownMergeSort ( int [] a , int [] b , int n ) { // Copiar inicialmente todo el array a en b copyArray ( a , 0 , n , b ); // Dividir y fusionar recursivamente el array b en a topDownSplitMerge ( a , 0 , n , b ); }

// Copia el array b en el array a void copyArray ( int [] b , int [] a , int n ) { for ( int i = 0 ; i < n ; i ++ ) { a [ i ] = b [ i ] ; } }// La carrera izquierda es a[izquierda : derecha-1]. // La carrera derecha es a[derecha : fin-1]. void bottomUpMerge ( int [] a , int izquierda , int derecha , int fin , int [] b ) { int i = izquierda ; int j = derecha ;// Mientras haya elementos en las secuencias izquierda o derecha... for ( int k = left ; k < end ; ++ k ) { // Si existe un encabezado de secuencia izquierda y es <= un encabezado de secuencia derecha existente. if ( i < right && ( j >= end || a [ i ] <= a [ j ] )) { b [ k ] = a [ i ] ; i = i + 1 ; } else { b [ k ] = a [ j ] ; j = j + 1 ; } } }void bottomUpMergeSort ( int [] a , int [] b , int n ) { // Cada secuencia de 1 elemento en a ya está "ordenada". // Crea secuencias ordenadas sucesivamente más largas de longitud 2, 4, 8, 16... hasta que todo el array esté ordenado. for ( int width = 1 ; width < n ; width *= 2 ) { // El array a está lleno de secuencias de longitud width. for ( int i = 0 ; i < n ; i = i + 2 * width ) { // Fusionar dos secuencias: a[i:i+width-1] y a[i+width:i+2*width-1] en b[] // o copiar a[i:n-1] en b[] (si (i+width >= n)) bottomUpMerge ( a , i , Math . min ( i + width , n ), Math . min ( i + 2 * width , n ), b ); } // Ahora el array de trabajo b está lleno de secuencias de longitud 2 * width. // Copiar el array b al array a para la siguiente iteración. // Una implementación más eficiente intercambiaría los roles de a y b. copyArray ( b , a , n ); } }

La función merge_sort( lista m) es // Caso base. Una lista de cero o un elemento está ordenada, por definición. Si la longitud de m ≤ 1, entonces devuelve m. // Caso recursivo. Primero, divide la lista en sublistas de igual tamaño // que consisten en 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 hacer si i < (longitud de m)/2 entonces agregar x a la izquierda demás agregar x a la derecha // Ordena recursivamente ambas sublistas. izquierda := merge_sort(izquierda) derecha := merge_sort(derecha) // A continuación, fusiona las sublistas ahora ordenadas. devolver fusión(izquierda, derecha)

La función merge(left, right) es var result := lista vacía mientras left no esté vacío y right no esté vacío , si first(left) ≤ first(right) entonces agregar primero(izquierdo) al resultado izquierda := resto(izquierda) demás agregar primero(derecha) al resultado derecha := resto(derecha) // Tanto el lado izquierdo como el derecho pueden tener elementos restantes; consúmalos. // (Solo se entrará en uno de los siguientes bucles). Mientras el lado izquierdo no esté vacío, haga lo siguiente: agregar primero(izquierdo) al resultado izquierda := resto(izquierda) mientras la derecha no esté vacía, haga agregar primero(derecha) al resultado derecha := resto(derecha) devolver resultado

función merge_sort( cabezal de nodo ) es // Devuelve si la lista está vacía si head = nil entonces devuelve nil var node array[32]; inicialmente todo nil var node result var node next var int i resultado := cabeza // fusionar nodos en un array mientras result ≠ nil hacer siguiente := resultado.siguiente; resultado.siguiente := nil para (i = 0; (i < 32) && (array[i] ≠ nil); i += 1) hacer resultado := fusionar(array[i], resultado) array[i] := nil // no sobrepasar el final del array si i = 32 entonces i -= 1 array[i] := resultado resultado := siguiente // fusionar el array en una sola lista resultado := nil para (i = 0; i < 32; i += 1) hacer resultado := fusionar(array[i], resultado) devolver resultado

mergeSort :: Ord a => [ a ] ​​-> [ a ] ​​mergeSort [] = [] mergeSort [ x ] = [ x ] mergeSort xs = merge ( mergeSort l , mergeSort r ) donde ( l , r ) = splitAt ( longitud xs ` div ` 2 ) xsfusionar :: Ord a => ([ a ], [ a ]) -> [ a ] ​​fusionar ( [] , xs ) = xs fusionar ( xs , [] ) = xs fusionar ( x : xs , y : ys ) | x <= y = x : fusionar ( xs , y : ys ) | de lo contrario = y : fusionar ( x : xs , ys )

En la ordenación de n objetos, la ordenación 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) de la ordenación 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 deduce de la definición del algoritmo (se aplica el algoritmo a dos listas de la mitad del tamaño de la lista original y se suman los n pasos necesarios para fusionar las dos listas resultantes). ^{[ 5 ]} La forma cerrada se deduce del teorema maestro para recurrencias de divide y vencerás . 

El número de comparaciones que realiza el algoritmo de ordenación por fusión en el peor de los casos viene dado por los números de ordenación . Estos números son iguales o ligeramente menores que ( n  ⌈ lg n ⌉ − 2 ^{⌈lg n ⌉} + 1), que se encuentra entre ( n lg n − n + 1) y ( n lg n + n + O(lg n )). ^{[ 6 ]} El mejor caso del algoritmo de ordenación por fusión requiere aproximadamente la mitad de iteraciones que el peor caso. ^{[ 7 ]}       

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

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

El algoritmo de ordenación por fusión es más eficiente que el algoritmo de ordenación rápida para ciertos tipos de listas si los datos a ordenar solo se pueden acceder de forma secuencial y eficiente, por lo que es popular en lenguajes como Lisp , donde las estructuras de datos de acceso secuencial son muy comunes. A diferencia de algunas implementaciones (eficientes) de ordenación rápida, el algoritmo de ordenación por fusión es un algoritmo de ordenación estable.

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

Un ordenamiento por fusión natural es similar a un ordenamiento por fusión ascendente, excepto que se explotan todas las secuencias ordenadas que aparecen de forma natural en la entrada. Se pueden explotar tanto secuencias monótonas como bitónicas (alternando hacia arriba/abajo), siendo las listas (o equivalentemente cintas o archivos) estructuras de datos convenientes (utilizadas como colas FIFO o pilas LIFO ). ^{[ 9 ]} En el ordenamiento por fusión ascendente, el punto de partida supone que cada secuencia tiene un elemento de longitud. En la práctica, los datos de entrada aleatorios tendrán muchas secuencias cortas que simplemente están ordenadas. En el caso típico, el ordenamiento por fusión natural puede no necesitar tantas pasadas porque hay menos secuencias que fusionar. En el mejor de los casos, la entrada ya está ordenada (es decir, es una sola secuencia), por lo que el ordenamiento por fusión natural solo necesita hacer una pasada a través de los datos. En muchos casos prácticos, hay secuencias naturales largas, y por esa razón el ordenamiento por fusión natural se explota como el componente clave de Timsort . Ejemplo:

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

Formalmente, se dice que el algoritmo de ordenación por fusión natural es Runs -óptimo, donde${\displaystyle {\mathtt {Corre}}(L)}$es el número de carreras en${\displaystyle L}$, menos uno.

Los algoritmos de ordenación por selección con reemplazo de torneo se utilizan para recopilar las ejecuciones iniciales para los algoritmos de ordenación 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 de nuevo en la memoria principal. Al hacerlo, se omite la operación de copia y se reduce a la mitad el número total de movimientos. 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 fue descrito más tarde ese mismo año como una optimización para la ordenación por 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 del algoritmo de ordenación por fusión, cuando se implementa en arreglos, es su requerimiento de 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 in situ :

• Kronrod (1969) sugirió una versión alternativa del algoritmo de 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 guardar un elemento del arreglo de entrada y espacio adicional para guardar O (1) punteros al arreglo 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 realizado varios intentos para producir un algoritmo de fusión in situ que pueda combinarse con una ordenación por fusión estándar (de arriba hacia abajo o de abajo hacia arriba) para producir una ordenación por fusión in situ. En este caso, la noción de "in situ" puede relajarse para significar "utilizar espacio de pila logarítmico", porque la ordenación 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 temporal , pero su algoritmo es complicado y tiene altos factores constantes: fusionar arreglos de longitud n y m puede tomar 5n + 12m + o ( m ) movimientos. ^{[ 14 ]} Este alto factor constante y el complicado algoritmo in situ se simplificaron y se hicieron más fáciles de entender. Bing-Chao Huang y Michael A. Langston [ ^{15 ] presentaron} un algoritmo de tiempo lineal directo de fusión in situ práctica 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 requiere un tiempo promedio ligeramente mayor que los algoritmos de ordenación por fusión estándar, libres para 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, es inestable para algunas listas. Pero utilizando conceptos similares, han podido resolver este problema. Otros algoritmos in situ incluyen SymMerge, que requiere un tiempo total de O (( n + m ) log ( n + m )) y es estable. ^{[ 16 ]} Incorporar dicho algoritmo a la ordenación por fusión aumenta su complejidad a la no linealítmica , pero aún cuasilineal , O ( n (log n ) ² ) .
• Muchas aplicaciones de ordenación externa utilizan una forma de ordenación por fusión en la que la entrada se divide en un mayor número de sublistas, idealmente en un número tal que su fusión permita que el conjunto de páginas que se está procesando actualmente quepa en la memoria principal.
• Una variante moderna, estable, lineal y de fusión in situ es la ordenación por fusión de bloques , que crea una sección de valores únicos para usar como espacio de intercambio.
• El espacio adicional requerido puede reducirse a O ( √n ) mediante búsquedas binarias y rotaciones. ^{[ 17 ]} Este método es empleado por la biblioteca STL de C++ y quadsort. ^{[ 12 ]}
• Una alternativa para reducir la copia en múltiples listas consiste en asociar un nuevo campo de información a cada clave (los elementos de m se denominan claves). Este campo se utilizará para vincular las claves y la información asociada en una lista ordenada (una clave y su información relacionada se denominan registro). A continuación, la fusión de las listas ordenadas se realiza modificando los valores de los enlaces; no es necesario mover ningún registro. Un campo que contiene solo un enlace suele ser más pequeño que un registro completo, por lo que también ocupa menos espacio. Esta es una técnica de ordenación estándar, no exclusiva de la ordenación por fusión.
• Una forma sencilla de reducir el espacio de almacenamiento a n /2 es mantener las partes izquierda y derecha como una estructura combinada, copiar solo la parte izquierda de m en un espacio temporal y dirigir la rutina de fusión para que coloque el resultado fusionado 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. El exceso de copias mencionado anteriormente también se reduce, ya que el último par de líneas antes de la instrucción de retorno del resultado (la función de fusión en el pseudocódigo anterior) se vuelve superfluo.

El algoritmo de ordenación por fusión externa es práctico para usar con unidades de disco o cinta cuando los datos 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 unidades de cinta utiliza cuatro unidades de cinta. Todas las operaciones de entrada/salida son secuenciales (excepto los rebobinados al final de cada pasada). Una implementación mínima puede funcionar con solo dos búferes de registro y unas pocas variables de programa.

Al denominar las cuatro unidades de cinta como A, B, C y 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 memoria. El algoritmo básico se puede describir de la siguiente manera:

1. Combinar pares de registros de A; escribir sublistas de dos registros alternativamente en C y D.
2. Fusionar las sublistas de dos registros de C y D en sublistas de cuatro registros; escribirlas alternativamente en A y B.
3. Fusionar las 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 log ₂ ( n ) pasadas.

En lugar de comenzar con secuencias muy cortas, generalmente se utiliza un algoritmo híbrido , donde la pasada inicial lee muchos registros en memoria, realiza una ordenación interna para crear una secuencia larga y luego distribuye esas secuencias largas en el conjunto de salida. Este paso evita muchas pasadas iniciales. Por ejemplo, una ordenación interna de 1024 registros ahorra nueve pasadas. La ordenación interna suele ser grande debido a esta ventaja. De hecho, existen técnicas que pueden hacer que las secuencias iniciales sean más largas que la memoria interna disponible. Una de ellas, el "quitanieves" de Knuth (basado en un min-heap binario ), genera secuencias dos veces más largas (en promedio) que el tamaño de la memoria utilizada. ^{[ 18 ]}

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

Un algoritmo de ordenación por fusión más sofisticado que optimiza el uso de las unidades de cinta (y disco) es la ordenación por fusión polifásica .

En los ordenadores modernos, la localidad de referencia puede ser de suma importancia en la optimización del software , debido al uso de jerarquías de memoria multinivel. Se han propuesto versiones del algoritmo de ordenación por fusión que tienen en cuenta la caché , cuyas operaciones se han elegido específicamente para minimizar el movimiento de páginas dentro y fuera de la caché de memoria de la máquina. Por ejemplo, elEl algoritmo de ordenación por fusión en mosaico deja de particionar submatrices cuando se alcanzan submatrices de tamaño S, donde S es el número de elementos de datos que caben en la caché de la CPU. Cada una de estas submatrices se ordena con un algoritmo de ordenación in situ, comola ordenación por inserción, para evitar intercambios de memoria, y luego se completa la ordenación por fusión normal de forma recursiva estándar. Este algoritmo ha demostrado un mejor rendimientoen máquinas que se benefician de la optimización de la caché.(LaMarca y Ladner, 1997)

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

// Ordena los elementos lo a hi (exclusivos) del array A. El algoritmo mergesort(A, lo, hi) es si lo+1 < hi entonces // Dos o más elementos. medio := ⌊(lo + hi) / 2⌋ bifurcar mergesort(A, lo, mid) mergesort(A, medio, alto) unir fusionar(A, lo, mid, hi)

/** * A: Matriz de entrada * B: Matriz de salida * lo: límite inferior * hola: límite superior * apagado: desplazamiento */ El algoritmo parallelMergesort(A, lo, hi, B, off) es longitud := alto - bajo + 1 Si len == 1, entonces  B[off] := A[lo]; de lo contrario , sea T[1..len] un nuevo array. medio := ⌊(lo + hi) / 2⌋ medio' := medio - bajo + 1 bifurcación paralelaMergesort(A, lo, mid, T, 1) parallelMergesort(A, mid + 1, hi, T, mid' + 1) unir parallelMerge(T, 1, mid', mid' + 1, len, B, off)

Ordenación por fusión multidireccional paralela

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

Idea básica

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

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

Además, los elementos de${\displaystyle S_{1,i},...,S_{p,i}}$se asignan al procesador${\displaystyle i}$, significa todos los elementos entre rango${\textstyle (i-1){\frac {n}{p}}}$y rango${\textstyle i{\frac {n}{p}}}$, que se distribuyen por todo${\displaystyle S_{i}}$Por lo tanto, cada procesador recibe una secuencia de secuencias ordenadas. El hecho de que el rango${\displaystyle k}$de los elementos divisores${\displaystyle v_{i}}$fue elegido a nivel mundial, proporciona dos propiedades importantes: Por un lado,${\displaystyle k}$fue elegido para que cada procesador pueda seguir funcionando en${\textstyle n/p}$elementos después de la asignación. El algoritmo está perfectamente equilibrado en carga . Por otro lado, todos los elementos en el procesador${\displaystyle i}$son menores o iguales que todos los elementos del procesador${\displaystyle i+1}$Por lo tanto, cada procesador realiza la fusión de p vías localmente y, de este modo, obtiene una secuencia ordenada a partir de sus subsecuencias. Debido a la segunda propiedad, no es necesario realizar ninguna otra fusión de p vías; los resultados solo deben ordenarse según el número de procesador.

Selección de secuencias múltiples

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

El algoritmo secuencial presentado devuelve los índices de las divisiones en cada secuencia, por ejemplo, los índices${\displaystyle l_{i}}$en secuencias${\displaystyle S_{i}}$de tal manera que${\displaystyle S_{i}[l_{i}]}$tiene un puesto global inferior a${\displaystyle k}$y${\displaystyle \mathrm {rank} \left(S_{i}[l_{i}+1]\right)\geq k}$. ^{[ 23 ]}

El algoritmo msSelect(S : Array of sorted Sequences [S_1,..,S_p], k : int) es para i = 1 a p hacer (l_i, r_i) = (0, |S_i|-1) mientras exista i: l_i < r_i hacer // seleccionar el elemento pivote en S_j[l_j], .., S_j[r_j], elegir j aleatoriamente de forma uniforme v := pickPivot(S, l, r) para i = 1 a p hacer m_i = binarySearch(v, S_i[l_i, r_i]) // secuencialmente Si m_1 + ... + m_p >= k entonces // m_1 + ... + m_p es el rango global de v r := m // asignación de vector demás l := m regresar l

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

Aplicado al algoritmo de ordenación por fusión multiway paralela, este algoritmo debe invocarse en paralelo de manera que todos los elementos divisores de rango${\textstyle i{\frac {n}{p}}}$para${\displaystyle i=1,..,p}$se encuentran simultáneamente. Estos elementos divisores se pueden utilizar para particionar cada secuencia en${\displaystyle p}$partes, con el mismo tiempo total de funcionamiento de${\displaystyle {\mathcal {O}}\left(p\,\log(n/p)\log(n)\right)}$.

Pseudocódigo

A continuación, se presenta el pseudocódigo completo del algoritmo de ordenación por fusión multivariante paralelo. Suponemos que existe una sincronización de barrera antes y después de la selección multisecuencia, de modo que cada procesador pueda determinar correctamente los elementos de división y la partición de la secuencia.

/** * d: Matriz de elementos sin ordenar * n: Número de elementos * p: Número de procesadores * devolver matriz ordenada */ algoritmo parallelMultiwayMergesort(d : Array, n : int, p : int) es o := new Array[0, n] // el array 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/p ordenar(S_i) // ordenar localmente sincronización v_i := msSelect([S_1,...,S_p], i * n/p) // elemento con rango global i * n/p sincronización (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 regresar o

Análisis

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

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

Adaptación y aplicación práctica

El algoritmo de ordenación por fusión multi-vía es muy escalable gracias a su alta capacidad de paralelización, que permite el uso de muchos procesadores. Esto lo convierte en una opción viable para ordenar grandes cantidades de datos, como los que se procesan en clústeres de computadoras . Además, dado que en estos 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, en estos sistemas entran en juego otros factores que no se tienen en cuenta al modelar en una PRAM . Aquí, es necesario 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 síncrono masivo para la ordenación por fusión multinivel y multidireccional, que divide${\displaystyle p}$procesadores en${\displaystyle r}$grupos de tamaño${\displaystyle p'}$. Todos los procesadores ordenan primero localmente. A diferencia del ordenamiento por fusión multidireccional de un solo nivel, estas secuencias luego se particionan en${\displaystyle r}$partes y asignadas a los grupos de procesadores apropiados. Estos pasos se repiten recursivamente en esos grupos. Esto reduce la comunicación y, en particular, evita problemas con muchos mensajes pequeños. La estructura jerárquica de la red real subyacente puede utilizarse para definir los grupos de procesadores (por ejemplo, racks , clústeres , etc.). ^{[ 22 ]}

Aunque heapsort tiene los mismos límites de tiempo que merge sort, requiere solo Θ(1) espacio auxiliar en lugar de Θ( n ) de merge sort. En arquitecturas modernas típicas, las implementaciones eficientes de quicksort generalmente superan a merge sort para ordenar arreglos basados ​​en RAM. ^{[ 27 ]} Se prefieren los quicksorts cuando el tamaño de los datos a ordenar es menor, ya que la complejidad espacial para quicksort es O(log n ), lo que ayuda a utilizar la localidad de caché mejor que merge sort (con complejidad espacial O(n)). ^{[ 27 ]} Por otro lado, merge sort es un ordenamiento estable y es más eficiente para manejar medios secuenciales de acceso lento. Merge sort suele ser 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 adicional, y el lento rendimiento de acceso aleatorio de una lista enlazada hace que algunos otros algoritmos (como quicksort) tengan un rendimiento deficiente, y otros (como heapsort) sean completamente imposibles.

A partir de Perl 5.8, el algoritmo de ordenación por fusión es el predeterminado (en versiones anteriores de Perl era quicksort). ^{[ 28 ]} En Java , los métodos Arrays.sort() utilizan la ordenación por fusión o una versión optimizada de quicksort según los tipos de datos y, para mayor eficiencia en la implementación, cambian a la ordenación por inserción cuando se ordenan menos de siete elementos de la matriz. ^{[ 29 ]} El kernel de Linux utiliza la ordenación 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 diversas plataformas y lenguajes de software, 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 del original el 7 de agosto de 2011. Recuperado el 4 de abril de 2009 .  . También ordenación por fusión práctica in situ . También
• 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 ordenación óptima 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". Actas del 8.º Simposio Anual ACM-SIAM sobre Algoritmos Discretos (SODA97) : 370–379 . CiteSeerX 10.1.1.31.1153 . 
• Skiena, Steven S. (2008). "4.5: Mergesort: Ordenación por divide y vencerás". The Algorithm Design Manual (2.ª  ed.). Springer. pp. 120–125 . ISBN  978-1-84800-069-8.
• Sun Microsystems. "API de matrices (Java SE 6)" . Consultado el 19 de noviembre de 2007 .
• Oracle Corp. "Arreglos (Java SE 10 y JDK 10)" . Consultado el 23 de julio de 2018 .

• Algoritmos de ordenación animados: Ordenación por fusió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 fusión , Pat Morin
• Programa en C para implementar el algoritmo de ordenación por fusión.
• Combinar código de ordenación con Java
• Programa en C++ para el algoritmo de ordenación por fusión