La ordenación por bloques , o por fusión de bloques , es un algoritmo de ordenación que combina al menos dos operaciones de fusión con una ordenación por inserción para llegar a un tiempo de ordenación estable in situ de O ( n log n ) (véase la notación Big O ) . Recibe su nombre de la observación de que fusionar dos listas ordenadas, A y B , es equivalente a dividir A en bloques de tamaño uniforme , insertar cada bloque A en B bajo reglas especiales y fusionar pares AB .
En 2008, Pok-Son Kim y Arne Kutzner propusieron un algoritmo práctico para la fusión in situ de O ( n log n ). [1]
El bucle externo de una ordenación por bloques es idéntico a una ordenación por fusión de abajo hacia arriba , donde cada nivel de la ordenación fusiona pares de submatrices, A y B , en tamaños de 1, luego 2, luego 4, 8, 16, y así sucesivamente, hasta que ambas submatrices combinadas forman la matriz en sí.
En lugar de fusionar A y B directamente como con los métodos tradicionales, un algoritmo de fusión basado en bloques divide A en bloques discretos de tamaño √ A (lo que da como resultado también √ A de bloques ), [2] inserta cada bloque A en B de modo que el primer valor de cada bloque A sea menor o igual (≤) al valor B inmediatamente posterior, luego fusiona localmente cada bloque A con cualquier valor B entre este y el siguiente bloque A.
Como las fusiones aún requieren un búfer separado lo suficientemente grande como para contener el bloque A que se va a fusionar, se reservan dos áreas dentro de la matriz para este propósito (conocidas como búferes internos ). [3] Los primeros dos bloques A se modifican para contener la primera instancia de cada valor dentro de A , con el contenido original de esos bloques desplazado si es necesario. Los bloques A restantes se insertan luego en B y se fusionan utilizando uno de los dos búferes como espacio de intercambio. Este proceso hace que los valores en ese búfer se reorganicen.
Una vez que se han fusionado todos los bloques A y B de cada submatriz A y B para ese nivel de ordenación por fusión, los valores de ese búfer deben ordenarse para restaurar su orden original, por lo que se debe aplicar una ordenación por inserción. A continuación, los valores de los búferes se redistribuyen a su primera posición ordenada dentro de la matriz. Este proceso se repite para cada nivel de la ordenación por fusión de abajo hacia arriba externa, momento en el que la matriz se habrá ordenado de forma estable.
En los ejemplos de código se utilizan los siguientes operadores:
Además, la ordenación por bloques se basa en las siguientes operaciones como parte de su algoritmo general:
Girar (matriz, cantidad, rango) Invertir (matriz, rango) Invertir (matriz, [rango.inicio, rango.inicio + cantidad)) Invertir (matriz, [rango.inicio + cantidad, rango.fin))
PisoPoderDeDos (x) x = x | (x >> 1) x = x | (x >> 2) x = x | (x >> 4) x = x | (x >> 8) x = x | (x >> 16) si (este es un sistema de 64 bits ) x = x | (x >> 32) devuelve x - (x >> 1)
Como se indicó anteriormente, el bucle externo de una ordenación por bloques es idéntico a una ordenación por combinación ascendente. Sin embargo, se beneficia de la variante que garantiza que cada submatriz A y B tenga el mismo tamaño dentro de un elemento:
Ordenamiento por bloques (matriz) potencia_de_dos = FloorPowerOfTwo (matriz.tamaño) escala = matriz.tamaño/potencia_de_dos // 1.0 ≤ escala < 2.0 // ordenación por inserción de 16 a 31 elementos a la vez para (combinar = 0; combinar < potencia_de_dos; combinar += 16) inicio = fusionar * escalar fin = inicio + 16 * escala InsertionSort (matriz, [inicio, fin)) para (longitud = 16; longitud < potencia_de_dos; longitud += longitud) para (fusión = 0; fusión < potencia_de_dos; fusión += longitud * 2) inicio = fusionar * escalar medio = (fusión + longitud) * escala fin = (fusión + longitud * 2) * escala if (array[end − 1] < array[start]) // los dos rangos están en orden inverso, por lo que una rotación es suficiente para fusionarlos Rotate (array, mid − start, [start, end)) else if (array[mid − 1] > array[mid]) Merge (array, A = [start, mid), B = [mid, end)) // de lo contrario los rangos ya están ordenados correctamente
También se puede utilizar la matemática de punto fijo , representando el factor de escala como una fracción integer_part + numerator/denominator:
Ordenamiento por bloques (matriz) potencia_de_dos = FloorPowerOfTwo (matriz.tamaño) denominador = potencia_de_dos/16 numerador_paso = array.size % denominador entero_paso = piso (matriz.tamaño/denominador) // ordenación por inserción de 16 a 31 elementos a la vez mientras (paso_entero < matriz.tamaño) parte_entera = numerador = 0 mientras (integer_part < array.size) // obtener los rangos para A y B inicio = parte_entera parte_entero += paso_entero numerador += numerador_paso si (numerador ≥ denominador) numerador −= denominador parte_entera++ medio = parte_entera parte_entero += paso_entero numerador += numerador_paso si (numerador ≥ denominador) numerador −= denominador parte_entera++ fin = parte_entera si (matriz[fin − 1] < matriz[inicio]) Rotar (matriz, centro − inicio, [inicio, fin)) de lo contrario si (matriz[centro − 1] > matriz[centro]) Fusionar (matriz, A = [inicio, centro), B = [centro, fin)) paso_entero += paso_entero paso_numerador += paso_numerador si (paso_numerador ≥ denominador) paso_numerador −= denominador paso_entero++
Los dos buffers internos necesarios para cada nivel del paso de fusión se crean moviendo las primeras 2 √ A primeras instancias de sus valores dentro de una submatriz A al inicio de A . Primero itera sobre los elementos en A y cuenta los valores únicos que necesita, luego aplica rotaciones de matriz para mover esos valores únicos al inicio. [6] Si A no contenía suficientes valores únicos para llenar los dos buffers (de tamaño √ A cada uno), B se puede usar igualmente. En este caso, mueve la última instancia de cada valor al final de B , y esa parte de B no se incluye durante las fusiones.
mientras (paso_entero < matriz.tamaño) tamaño_de_bloque = √ paso_entero tamaño_de_buffer = paso_entero/tamaño_de_bloque + 1 [extraer dos buffers de tamaño 'buffer_size' cada uno]
Si B tampoco contiene suficientes valores únicos, extrae la mayor cantidad de valores únicos que pueda encontrar y luego ajusta el tamaño de los bloques A y B de modo que la cantidad de bloques A resultantes sea menor o igual que la cantidad de elementos únicos extraídos para el búfer. En este caso, solo se utilizará un búfer; el segundo búfer no existirá.
buffer_size = [número de valores únicos encontrados]tamaño_de_bloque = paso_entero/tamaño_de_búfer + 1 parte_entera = numerador = 0mientras (integer_part < array.size) [obtener los rangos para A y B] [ajustar A y B para que no incluyan los rangos utilizados por los buffers]
Una vez que se han creado uno o dos buffers internos, comienza a fusionar cada submatriz A y B para este nivel de ordenación por fusión. Para ello, divide cada submatriz A y B en bloques de tamaño uniforme calculados en el paso anterior, donde el primer bloque A y el último bloque B tienen un tamaño desigual si es necesario. A continuación, recorre cada uno de los bloques A de tamaño uniforme e intercambia el segundo valor con un valor correspondiente del primero de los dos buffers internos. Esto se conoce como etiquetar los bloques.
// blockA es el rango de los bloques A restantes, // y firstA es el primer bloque A de tamaño desigualbloqueA = [A.inicio, A.fin)firstA = [A.inicio, A.inicio + |bloqueA| % tamaño_bloque) // intercambia el segundo valor de cada bloque A con el valor en buffer1 para (índice = 0, índiceA = firstA.end + 1; índiceA < bloqueA.end; índiceA += tamaño_bloque) Intercambia (matriz[buffer1.start + índice], matriz[índiceA]) índice++ últimoA = primeroAblockB = [B.inicio, B.inicio + mínimo (tamaño_bloque, |B|))bloqueA.inicio += |primerA|
Después de definir y etiquetar los bloques A de esta manera, los bloques A pasan a través de los bloques B intercambiando el primer bloque A de tamaño uniforme con el siguiente bloque B. Este proceso se repite hasta que el primer valor del bloque A con el valor de etiqueta más pequeño sea menor o igual que el último valor del bloque B que se acaba de intercambiar con un bloque A.
En ese punto, el bloque A mínimo (el bloque A con el valor de etiqueta más pequeño) se intercambia al inicio de los bloques A que se van acumulando y el valor etiquetado se restaura con su valor original del primer búfer. Esto se conoce como dejar atrás un bloque, ya que ya no se acumulará junto con los bloques A restantes. Luego, ese bloque A se inserta en el bloque B anterior, primero mediante una búsqueda binaria en B para encontrar el índice donde el primer valor de A es menor o igual que el valor en ese índice de B, y luego rotando A en B en ese índice.
minA = bloqueA.inicio índiceA = 0 mientras (verdadero) // si hay un bloque B anterior y el primer valor del bloque A mínimo es ≤ // el último valor del bloque B anterior, entonces descarta ese bloque A mínimo detrás. // o si no quedan bloques B, sigue descartando los bloques A restantes. if ((|lastB| > 0 and array[lastB.end - 1] ≥ array[minA]) or |blockB| = 0) // determina dónde dividir el bloque B anterior y rótalo en la división B_split = BinaryFirst (array, array[minA], lastB) B_restante = últimoB.fin - B_dividido // intercambia el bloque A mínimo con el comienzo de los bloques A continuos BlockSwap (array, blockA.start, minA, block_size) // restaurar el segundo valor para el bloque A Swap (array[blockA.start + 1], array[buffer1.start + indexA]) índiceA++ // rotar el bloque A en el bloque B anterior Rotate (array, blockA.start - B_split, [B_split, blockA.start + block_size)) // fusionar localmente el bloque A anterior con los valores B que le siguen, // usando el segundo buffer interno como espacio de intercambio (si existe) if (|buffer2| > 0) MergeInternal (array, lastA, [lastA.end, B_split), buffer2) else MergeInPlace (array, lastA, [lastA.end, B_split)) // actualiza el rango de los bloques A restantes, // y el rango restante del bloque B después de que se dividió lastA = [bloqueA.inicio - B_restante, bloqueA.inicio - B_restante + tamaño_bloque) lastB = [lastA.fin, lastA.fin + B_restante) // si no quedan más bloques A, este paso finaliza bloqueA.inicio = bloqueA.inicio + tamaño_bloque si (|blockA| = 0) romper minA = [nuevo bloque A mínimo] (ver abajo) else if (|blockB| < block_size) // mover el último bloque B, que tiene un tamaño desigual, // antes de los bloques A restantes, usando una rotación Rotate (array, blockB.start - blockA.start, [blockA.start, blockB.end)) últimoB = [bloqueA.inicio, bloqueA.inicio + |bloqueB|) bloqueA.inicio += |bloqueB| bloqueA.fin += |bloqueB| minA += |bloqueB| bloqueB.fin = bloqueB.inicio de lo contrario // haga rodar el bloque A más a la izquierda hasta el final intercambiándolo con el siguiente bloque B BlockSwap (array, blockA.start, blockB.start, block_size) últimoB = [bloqueA.inicio, bloqueA.inicio + tamaño_bloque) si (minA = bloqueA.inicio) minA = bloqueA.fin blockA.start += tamaño_bloque blockA.end += tamaño_bloque blockB.start += tamaño_bloque // esto es equivalente al mínimo (blockB.end + block_size, B.end), // pero tiene el potencial de desbordarse si (blockB.end > B.end - block_size) bloqueB.fin = B.fin demás blockB.end += tamaño_bloque // fusionar el último bloque A con los valores B restantes si (|buffer2| > 0) MergeInternal (array, lastA, [lastA.end, B.end), buffer2) de lo contrario MergeInPlace (array, lastA, [lastA.end, B.end))
Una optimización que se puede aplicar durante este paso es la técnica de agujero flotante . [7] Cuando el bloque A mínimo se deja atrás y necesita rotarse en el bloque B anterior, después de lo cual su contenido se intercambia en el segundo búfer interno para las fusiones locales, sería más rápido intercambiar el bloque A al búfer de antemano y aprovechar el hecho de que el contenido de ese búfer no necesita conservar ningún orden. Entonces, en lugar de rotar el segundo búfer (que solía ser el bloque A antes del intercambio de bloques) en el bloque B anterior en la posición índice , los valores en el bloque B después del índice simplemente se pueden intercambiar en bloque con los últimos elementos del búfer.
El agujero flotante en este caso se refiere al contenido del segundo buffer interno que flota alrededor de la matriz y actúa como un agujero en el sentido de que los elementos no necesitan conservar su orden.
Una vez que el bloque A se ha rotado en el bloque B, el bloque A anterior se fusiona con los valores B que lo siguen, utilizando el segundo búfer como espacio de intercambio. Cuando el primer bloque A se coloca detrás, esto se refiere al bloque A de tamaño desigual al principio, cuando el segundo bloque A se coloca detrás, esto se refiere al primer bloque A, y así sucesivamente.
MergeInternal (array, A, B, buffer) // intercambia en bloque los valores en A con los de 'buffer' BlockSwap (array, A.start, buffer.start, |A|) A_count = 0, B_count = 0, inserción = 0 mientras (A_count < |A| y B_count < |B|) si (matriz[buffer.start + A_count] ≤ matriz[B.start + B_count]) Intercambiar (matriz[A.start + insert], matriz[buffer.start + A_count]) Un_cuenta++ de lo contrario, intercambiar (matriz[A.inicio + inserción], matriz[B.inicio + B_cuenta]) B_cuenta++ insertar++ // intercambia el bloque de la parte restante del buffer con la parte restante de la matriz BlockSwap (matriz, buffer.start + A_count, A.start + insert, |A| - A_count)
Si el segundo búfer no existe, se debe realizar una operación de fusión estrictamente en el lugar, como una versión basada en rotación del algoritmo de Hwang y Lin, [7] [8] el algoritmo de Dudzinski y Dydek, [9] o una búsqueda binaria repetida y rotación.
MergeInPlace (array, A, B) while (|A| > 0 and |B| > 0) // encuentra el primer lugar en B donde se debe insertar el primer elemento en A mid = BinaryFirst (array, array[A.start], B) // rotar A a su lugar cantidad = medio - A.fin Girar (matriz, cantidad, [A.inicio, medio)) // Calcular los nuevos rangos A y B B = [medio, B.fin) A = [A.inicio + cantidad, medio) A.inicio = BinaryLast (matriz, matriz[A.inicio], A)
Después de descartar el bloque A mínimo y fusionar el bloque A anterior con los valores B que lo siguen, el nuevo bloque A mínimo debe encontrarse dentro de los bloques que aún se están moviendo a través de la matriz. Esto se maneja ejecutando una búsqueda lineal a través de esos bloques A y comparando los valores de las etiquetas para encontrar el más pequeño.
minA = blockA.start for (findA = minA + block_size; findA < blockA.end - 1; findA += block_size) if (matriz[findA + 1] < matriz[minA + 1]) minA = encontrarA
Los bloques A restantes continúan su recorrido por la matriz y se eliminan y se insertan donde pertenecen. Este proceso se repite hasta que todos los bloques A se eliminan y se rotan hacia el bloque B anterior.
Una vez que el último bloque A restante se ha dejado atrás y se ha insertado en B, donde corresponde, se lo debe fusionar con los valores B restantes que lo siguen. Esto completa el proceso de fusión para ese par particular de submatrices A y B. Sin embargo, luego debe repetirse el proceso para las submatrices A y B restantes para el nivel actual de la ordenación por fusión.
Tenga en cuenta que los buffers internos se pueden reutilizar para cada conjunto de submatrices A y B para este nivel de ordenamiento por combinación, y no es necesario volver a extraerlos ni modificarlos de ninguna manera.
Una vez fusionadas todas las submatrices A y B, todavía quedan uno o dos búferes internos. El primer búfer interno se utilizó para etiquetar los bloques A y su contenido sigue estando en el mismo orden que antes, pero es posible que el contenido del segundo búfer interno se haya reorganizado cuando se utilizó como espacio de intercambio para las fusiones. Esto significa que el contenido del segundo búfer deberá ordenarse utilizando un algoritmo diferente, como la ordenación por inserción. A continuación, los dos búferes deben redistribuirse nuevamente en la matriz utilizando el proceso opuesto al que se utilizó para crearlos.
Después de repetir estos pasos para cada nivel de la ordenación por fusión de abajo hacia arriba, se completa la ordenación por bloques.
La ordenación por bloques funciona extrayendo dos búferes internos, dividiendo los subconjuntos A y B en bloques de tamaño uniforme, colocando y soltando los bloques A en B (usando el primer búfer para seguir el orden de los bloques A), fusionando localmente usando el segundo búfer como espacio de intercambio, ordenando el segundo búfer y redistribuyendo ambos búferes. Si bien los pasos no cambian, estos subsistemas pueden variar en su implementación real.
Una variante de la ordenación por bloques le permite utilizar cualquier cantidad de memoria adicional que se le proporcione, utilizando este búfer externo para fusionar un subarreglo A o un bloque A con B siempre que A quepa en él. En esta situación, sería idéntico a una ordenación por fusión.
Algunas buenas opciones para el tamaño del búfer incluyen:
En lugar de etiquetar los bloques A utilizando el contenido de uno de los buffers internos, se puede utilizar un buffer de imitación de movimiento indirecto. [1] [10] Este es un buffer interno definido como s1 t s2 , donde s1 y s2 son cada uno tan grandes como el número de bloques A y B, y t contiene cualquier valor inmediatamente posterior a s1 que sea igual al último valor de s1 (lo que garantiza que ningún valor en s2 aparezca en s1 ). Todavía se utiliza un segundo buffer interno que contiene valores únicos de √ A. Los primeros valores de √ A de s1 y s2 se intercambian entre sí para codificar información en el buffer sobre qué bloques son bloques A y cuáles son bloques B. Cuando un bloque A en el índice i se intercambia con un bloque B en el índice j (donde el primer bloque A de tamaño uniforme está inicialmente en el índice 0), s1[i] y s1[j] se intercambian con s2[i] y s2[j], respectivamente. Esto imita los movimientos de los bloques A a través de B. Los valores únicos en el segundo búfer se utilizan para determinar el orden original de los bloques A a medida que pasan a través de los bloques B. Una vez que se han descartado todos los bloques A, el búfer de imitación de movimiento se utiliza para decodificar si un bloque dado en la matriz es un bloque A o un bloque B, cada bloque A se rota en B y el segundo búfer interno se utiliza como espacio de intercambio para las fusiones locales.
No es necesario etiquetar necesariamente el segundo valor de cada bloque A: se puede usar el primero, el último o cualquier otro elemento en su lugar. Sin embargo, si se etiqueta el primer valor, será necesario leer los valores desde el primer búfer interno (donde se intercambiaron) al decidir dónde colocar el bloque A mínimo.
Se pueden utilizar muchos algoritmos de ordenamiento para ordenar el contenido del segundo búfer interno, incluidos los ordenamientos inestables como quicksort , ya que se garantiza que el contenido del búfer es único. No obstante, se sigue recomendando el ordenamiento por inserción por su rendimiento situacional y su falta de recursión.
Las implementaciones conocidas de clasificación de bloques incluyen:
La ordenación por bloques es una clase de algoritmos bien definidos y comprobables, con implementaciones funcionales disponibles como combinación y como ordenación. [11] [15] [12] Esto permite medir y considerar sus características.
La ordenación por bloques comienza realizando una ordenación por inserción en grupos de 16 a 31 elementos de la matriz. La ordenación por inserción es una operación, por lo que esto lleva a cualquier valor entre hasta , que es una vez que se omiten los factores constantes . También debe aplicar una ordenación por inserción en el segundo búfer interno después de que se complete cada nivel de fusión. Sin embargo, como este búfer estaba limitado a en tamaño, la operación también termina siendo .
A continuación, debe extraer dos buffers internos para cada nivel de ordenación por combinación. Para ello, itera sobre los elementos de las submatrices A y B e incrementa un contador cada vez que cambia el valor y, al encontrar suficientes valores, los rota hasta el inicio de A o el final de B. En el peor de los casos, esto terminará buscando en toda la matriz antes de encontrar valores únicos no contiguos, lo que requiere comparaciones y rotaciones de valores. Esto se resuelve en , o .
Cuando ninguno de los subconjuntos A o B contenía valores únicos para crear los buffers internos, se realiza una operación de fusión en el lugar normalmente subóptima donde se realizan búsquedas binarias repetidas y se rota A en B. Sin embargo, la falta conocida de valores únicos dentro de cualquiera de los subconjuntos impone un límite estricto en la cantidad de búsquedas binarias y rotaciones que se realizarán durante este paso, que nuevamente es elementos rotados hasta veces, o . El tamaño de cada bloque también se ajusta para que sea más pequeño en el caso en que se encuentren valores únicos pero no 2 , lo que limita aún más la cantidad de valores únicos contenidos dentro de cualquier bloque A o B.
El etiquetado de los bloques A se realiza varias veces para cada submatriz A, luego los bloques A se transfieren y se insertan en los bloques B hasta veces. Las fusiones locales conservan la misma complejidad de una fusión estándar, aunque con más asignaciones ya que los valores deben intercambiarse en lugar de copiarse. La búsqueda lineal para encontrar el nuevo bloque A mínimo se repite varias veces en bloques . Y el proceso de redistribución del búfer es idéntico a la extracción del búfer, pero a la inversa, y por lo tanto tiene la misma complejidad.
Después de omitir todos los valores de complejidad más alta y considerando que hay niveles en el bucle de fusión externo, esto conduce a una complejidad asintótica final de para los casos peores y promedio. Para el mejor caso, donde los datos ya están en orden, el paso de fusión realiza comparaciones para el primer nivel, luego , , , etc. Esta es una serie matemática bien conocida que se resuelve en .
Como la ordenación por bloques no es recursiva y no requiere el uso de asignaciones dinámicas , esto conduce a un espacio de pila y montón constante. Utiliza memoria auxiliar O(1) en un modelo transdicotómico , que acepta que los O(log n ) bits necesarios para realizar un seguimiento de los rangos de A y B no pueden ser mayores que 32 o 64 en sistemas informáticos de 32 o 64 bits, respectivamente, y, por lo tanto, se simplifica a espacio O(1) para cualquier matriz que se pueda asignar de manera factible.
Aunque los elementos de la matriz se mueven fuera de orden durante una ordenación en bloque, cada operación es totalmente reversible y habrá restaurado el orden original de los elementos equivalentes al completarse.
La estabilidad requiere que la primera instancia de cada valor en una matriz antes de la ordenación siga siendo la primera instancia de ese valor después de la ordenación. La ordenación por bloques mueve estas primeras instancias al inicio de la matriz para crear los dos búferes internos, pero cuando se completan todas las fusiones para el nivel actual de la ordenación por bloques, esos valores se distribuyen nuevamente a la primera posición ordenada dentro de la matriz. Esto mantiene la estabilidad.
Antes de pasar los bloques A a través de los bloques B, cada bloque A tiene su segundo valor intercambiado con un valor del primer búfer. En ese punto, los bloques A se mueven fuera de orden para pasar a través de los bloques B. Sin embargo, una vez que encuentra dónde debe insertar el bloque A más pequeño en el bloque B anterior, ese bloque A más pequeño se mueve de nuevo al inicio de los bloques A y su segundo valor se restaura. Para cuando se hayan insertado todos los bloques A, los bloques A estarán en orden nuevamente y el primer búfer contendrá sus valores originales en el orden original.
El uso del segundo búfer como espacio de intercambio al fusionar un bloque A con algunos valores B hace que el contenido de ese búfer se reorganice. Sin embargo, como el algoritmo ya se aseguró de que el búfer solo contenga valores únicos, ordenar el contenido del búfer es suficiente para restaurar su orden estable original.
La ordenación por bloques es una ordenación adaptativa en dos niveles: primero, omite la fusión de los subconjuntos A y B que ya están ordenados. A continuación, cuando es necesario fusionar A y B y se dividen en bloques de tamaño uniforme, los bloques A solo se desplazan hasta B hasta donde sea necesario, y cada bloque solo se fusiona con los valores B que lo siguen inmediatamente. Cuanto más ordenados estaban originalmente los datos, menos valores B habrá que fusionar en A.
La ordenación por bloques es una ordenación estable que no requiere memoria adicional, lo que resulta útil en casos en los que no hay suficiente memoria libre para asignar el búfer O(n). Cuando se utiliza la variante de búfer externo de la ordenación por bloques, se puede escalar desde el uso de memoria O(n) hasta búferes progresivamente más pequeños según sea necesario, y seguirá funcionando de manera eficiente dentro de esas limitaciones.
La ordenación por bloques no explota rangos ordenados de datos en un nivel tan fino como otros algoritmos, como Timsort . [16] Solo verifica estos rangos ordenados en los dos niveles predefinidos: los subarreglos A y B, y los bloques A y B. También es más difícil de implementar y paralelizar en comparación con una ordenación por fusión.
