Ordenación por fusión

Algoritmo de ordenamiento divide y vencerás

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 hacia arriba aparecieron en un informe de Goldstine y von Neumann ya en 1948. ^[4]

Algoritmo

Conceptualmente, una ordenación por fusió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.

Implementación de arriba hacia abajo

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 ); // ordena los 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 []) { for ( k = iBegin ; k < iEnd ; k ++ ) B [ k ] = A [ k ]; }               

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

Implementación de abajo hacia arriba

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 ; } } }                                                          void CopyArray ( B [], A [], n ) { para ( i = 0 ; i < n ; i ++ ) A [ i ] = B [ i ]; }              

Implementación de arriba hacia abajo utilizando listas

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.

function merge_sort( list 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 := empty list var right := empty list for each x with index i in 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

Implementación de abajo hacia arriba utilizando listas

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

Implementación de arriba hacia abajo en un estilo declarativo

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 )                                                          

Análisis

Un algoritmo de ordenamiento por combinación recursivo que se utiliza para ordenar una matriz de 7 valores enteros. Estos son los pasos que seguiría un humano para emular el ordenamiento por combinación (de arriba hacia abajo).

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}}\approx 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).

Ordenación por fusión natural

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 {Runs}}(L)}$ ${\displaystyle L}$

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

Ordenación por combinación de ping-pong

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]

Ordenación por combinación en el lugar

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 bloques , 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.

Uso con unidades de cinta

Los algoritmos de ordenación por fusión permitieron ordenar grandes conjuntos de datos en las primeras computadoras que tenían memorias de acceso aleatorio pequeñas según los estándares modernos. Los registros se almacenaban en cintas magnéticas y se procesaban en bancos de unidades de cinta magnética, como estas IBM 729 .

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 de ₂ ( 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 .

Optimización de la ordenación por combinación

Ordenación por combinación en mosaico aplicada a una matriz de números enteros aleatorios. El eje horizontal es el índice de la matriz y el eje vertical es el número entero.

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)

Ordenación por fusión paralela

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 .

Ordenación por fusión con recursión paralela

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)}$

Ordenación por fusión con fusión paralela

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{sort}}(n)=T_{\infty }^{\text{sort}}\left({\frac {n}{2}}\right)+T_{\infty }^{\text{merge}}(n)=T_{\infty }^{\text{sort}}\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{sort}}=\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)}$

Ordenación por combinación de múltiples vías paralelas

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]} ${\displaystyle k}$

Idea básica

El proceso de combinación y ordenación multidireccional paralela en cuatro procesadores a . ${\displaystyle t_{0}}$ ${\displaystyle t_{3}}$

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 . ${\displaystyle n}$ ${\displaystyle p}$ ${\displaystyle S_{1},...,S_{p}}$ ${\textstyle \lceil {\frac {n}{p}}\rceil }$ ${\displaystyle n}$ ${\displaystyle 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}}$ ${\displaystyle S_{i}}$ ${\displaystyle S_{i}}$ ${\displaystyle p}$ ${\displaystyle S_{i,1},...,S_{i,p}}$ ${\textstyle S_{i,j}:=\{x\in S_{i}|rank(v_{j-1})<rank(x)\leq rank(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 modo 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}}$ ${\displaystyle i}$ ${\textstyle (i-1){\frac {n}{p}}}$ ${\textstyle i{\frac {n}{p}}}$ ${\displaystyle S_{i}}$ ${\displaystyle k}$ ${\displaystyle v_{i}}$ ${\displaystyle k}$ ${\textstyle n/p}$ ${\displaystyle i}$ ${\displaystyle i+1}$

Selección de múltiples secuencias

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. ${\displaystyle p}$ ${\displaystyle S_{1},...,S_{p}}$ ${\displaystyle p}$ ${\displaystyle k}$ ${\displaystyle x}$ ${\displaystyle k}$ ${\displaystyle S_{i}}$ ${\displaystyle l_{i}}$ ${\displaystyle x}$ ${\displaystyle 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] ${\displaystyle l_{i}}$ ${\displaystyle S_{i}}$ ${\displaystyle S_{i}[l_{i}]}$ ${\displaystyle k}$ ${\displaystyle \mathrm {rank} \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 . ${\displaystyle p}$ ${\displaystyle {\mathcal {O}}\left(p\log \left(n/p\right)\right)}$ ${\displaystyle {\mathcal {O}}\left(\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}$ ${\displaystyle p}$ ${\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 ordenamiento por fusión multidireccional en paralelo. Suponemos que existe una sincronización de barrera antes y después de la selección de múltiples secuencias, 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

Análisis

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 ${\displaystyle n/p}$ ${\displaystyle {\mathcal {O}}\left(n/p\;\log(n/p)\right)}$ ${\displaystyle {\mathcal {O}}\left(p\,\log(n/p)\log(n)\right)}$ ${\displaystyle p}$ ${\displaystyle {\mathcal {O}}(\log(p)\;n/p)}$

${\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 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 multinivel y multidireccional de un solo nivel, estas secuencias se dividen en partes y se asignan a los grupos de procesadores apropiados. Estos pasos se repiten de forma recursiva 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] ${\displaystyle p}$ ${\displaystyle r}$ ${\displaystyle p'}$ ${\displaystyle r}$

Otras variantes

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]

Comparación con otros algoritmos de ordenación

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 anteriormente fue utilizado por Python desde la versión 2.3 a la versión 3.10. ^[32]

Referencias

1. Skiena (2008, pág. 122)
2. Goodrich, Michael T.; Tamassia, Roberto; Goldwasser, Michael H. (2013). "Capítulo 12 - Ordenamiento y selección". Estructuras de datos y algoritmos en Python (1.ª ed.). Hoboken [NJ]: Wiley. págs. 538–549. ISBN 978-1-118-29027-9.
3. Knuth (1998, pág. 158)
4. Katajainen, Jyrki; Träff, Jesper Larsson (marzo de 1997). "Algoritmos y complejidad". Actas de la 3.ª Conferencia italiana sobre algoritmos y complejidad . Conferencia italiana sobre algoritmos y complejidad. Apuntes de clase en informática. Vol. 1203. Roma. págs. 217–228. CiteSeerX 10.1.1.86.3154 . doi :10.1007/3-540-62592-5_74. ISBN.  978-3-540-62592-6.
5. Cormen y otros (2009, pág. 36)
6. El número del peor caso dado aquí no coincide con el que se da en Knuth 's Art of Computer Programming , Vol 3. La discrepancia se debe a que Knuth analizó una implementación variante de ordenación por combinación que es ligeramente subóptima.
7. Jayalakshmi, N. (2007). Estructura de datos con C++. Firewall Media. ISBN 978-81-318-0020-1.OCLC 849900742  .
8. Cormen et al. (2009, pág.151)
9. Powers, David MW; McMahon, Graham B. (1983). "Un compendio de programas prolog interesantes". Informe técnico 8313 del DCS (informe). Departamento de Ciencias de la Computación, Universidad de Nueva Gales del Sur.
10. "WikiSort. Algoritmo de ordenación rápido y estable que utiliza memoria O(1). Dominio público". GitHub . 14 de abril de 2014.
11. Chandramouli, Badrish; Goldstein, Jonathan (2014). La paciencia es una virtud: reconsideración de la combinación y la clasificación en los procesadores modernos (PDF) . SIGMOD/PODS.
12. "Quadsort es una ordenación por fusión adaptativa estable y sin ramificaciones". GitHub . 8 de junio de 2022.
13. Katajainen, Pasanen y Teuhola (1996)
14. Geffert, Viliam; Katajainen, Jyrki; Pasanen, Tomi (2000). "Fusión in situ asintóticamente eficiente". Ciencias de la computación teórica . 237 (1–2): 159–181. doi : 10.1016/S0304-3975(98)00162-5 .
15. Huang, Bing-Chao; Langston, Michael A. (marzo de 1988). "Fusión práctica in situ". Comunicaciones de la ACM . 31 (3): 348–352. doi : 10.1145/42392.42403 . S2CID  4841909.
16. Kim, Pok-Son; Kutzner, Arne (2004). "Fusión de almacenamiento mínimo estable mediante comparaciones simétricas". Algoritmos – ESA 2004. Simposio Europeo de Algoritmos. Apuntes de clase en Ciencias de la Computación. Vol. 3221. págs. 714–723. CiteSeerX 10.1.1.102.4612 . doi :10.1007/978-3-540-30140-0_63. ISBN  978-3-540-23025-0.
17. Kim, Pok-Son; Kutzner, Arne (1 de septiembre de 2003). "Un nuevo método para la fusión eficiente en el lugar". Actas de la Conferencia del Instituto Coreano de Sistemas Inteligentes : 392–394.
18. Ferragina, Paolo (2009–2019), "5. Ordenar elementos atómicos" (PDF) , La magia de los algoritmos! , p. 5-4, archivado (PDF) desde el original el 2021-05-12
19. Cormen et al. (2009, págs. 797–805)
20. Victor J. Duvanenko "Parallel Merge Sort" Diario y blog del Dr. Dobb [1] e implementación de C++ en el repositorio de GitHub [2]
21. Peter Sanders; Johannes Singler (2008). "Conferencia Algoritmos paralelos" (PDF) . Consultado el 2 de mayo de 2020 .
22. Axtmann, Michael; Bingmann, Timo; Sanders, Peter; Schulz, Christian (2015). "Ordenamiento masivo paralelo práctico". Actas del 27.º simposio de la ACM sobre paralelismo en algoritmos y arquitecturas . págs. 13-23. doi :10.1145/2755573.2755595. ISBN . 9781450335881.S2CID18249978  .​
23. Peter Sanders (2019). "Conferencia Algoritmos paralelos" (PDF) . Consultado el 2 de mayo de 2020 .
24. Cole, Richard (agosto de 1988). "Ordenación por fusión paralela". SIAM J. Comput . 17 (4): 770–785. CiteSeerX 10.1.1.464.7118 . doi :10.1137/0217049. S2CID  2416667. 
25. Powers, David MW (1991). "Parallelized Quicksort and Radixsort with Optimal Speedup". Actas de la Conferencia Internacional sobre Tecnologías de Computación Paralela, Novosibirsk . Archivado desde el original el 25 de mayo de 2007.
26. Powers, David MW (enero de 1995). Unificación paralela: complejidad práctica (PDF) . Taller de arquitectura informática de Australasia, Universidad de Flinders.
27. Oladipupo, Esau Taiwo; Abikoye, Oluwakemi Christianah (2020). "Comparación de quicksort y mergesort". Tercera Conferencia Internacional sobre Computación y Comunicaciones en Red (CoCoNet 2019) . 2020 (2020): 9. Consultado el 20 de enero de 2024 a través de Elsevier Science Direct.
28. "Sort – Documentación de Perl 5 versión 8.8" . Consultado el 23 de agosto de 2020 .
29. coleenp (22 de febrero de 2019). "src/java.base/share/classes/java/util/Arrays.java @ 53904:9c3fe09f69bc". OpenJDK .
30. kernel de linux /lib/list_sort.c
31. Universidad de Liverpool (12 de diciembre de 2022). "Los informáticos mejoran la función de ordenación de Python". Tech Xplore . Consultado el 8 de mayo de 2024 .
32. James, Mike (21 de diciembre de 2022). "Python ahora usa Powersort". i-programmer.info . Consultado el 8 de mayo de 2024 .

Bibliografía

• 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 memorias caché 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.ª edición). Springer. Págs. 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 .

Enlaces externos

• 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