Orden de bloque - Block sort

Orden de bloque

Clasificar bloques de forma estable clasificando los números del 1 al 16. Insertar grupos de clasificación de 16, extraer dos búferes internos, etiquetar los bloques A (de tamaño √ 16 = 4 cada uno), pasar los bloques A por B , combinarlos localmente, clasificar el segundo búfer, y redistribuir los búferes.
Clase	Algoritmo de clasificación
Estructura de datos	Formación
Rendimiento en el peor de los casos	O ( n log n )
Rendimiento en el mejor de los casos	O ( n )
Rendimiento medio	O ( n log n )
Complejidad espacial en el peor de los casos	O (1)

La clasificación por bloques , o clasificación por combinación de bloques , es un algoritmo de clasificación que combina al menos dos operaciones de combinación con una clasificación por inserción para llegar a una clasificación estable en el lugar O ( n log n ) . 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 .

Un algoritmo práctico para la fusión de O (log n) en el lugar fue propuesto por Pok-Son Kim y Arne Kutzner en 2008.

Visión general

El bucle exterior de la clasificación de bloques es idéntico a una clasificación de fusión ascendente , donde cada nivel de la clasificación fusiona pares de subarreglos, A y B , en tamaños de 1, luego 2, luego 4, 8, 16, y así sucesivamente. hasta que ambas submatrices combinadas sean la propia matriz.

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 √ Un número de bloques también), inserta cada bloque A en B de manera que el primer valor de cada bloque A es menor o igual (≤) al valor B inmediatamente después, luego fusiona localmente cada bloque A con cualquier valor B entre él 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 fusionará, se reservan dos áreas dentro de la matriz para este propósito (conocidas como búferes internos ). Por tanto, los dos primeros 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 en B y se combinan 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 todos los bloques A y B de cada subarreglo A y B se han fusionado para ese nivel de clasificación de fusión, los valores en ese búfer deben ordenarse para restaurar su orden original, por lo que se debe aplicar una clasificación de inserción. Los valores en los búferes luego se redistribuyen a su primera posición ordenada dentro de la matriz. Este proceso se repite para cada nivel de la clasificación de combinación ascendente externa, en cuyo punto la matriz se habrá ordenado de manera estable.

Algoritmo

Los siguientes operadores se utilizan en los ejemplos de código:

Además, la clasificación de bloques se basa en las siguientes operaciones como parte de su algoritmo general:

• Swap : intercambia las posiciones de dos valores en una matriz.
• Intercambio de bloques : intercambia un rango de valores dentro de una matriz con valores en un rango diferente de la matriz.
• Búsqueda binaria : asumiendo que la matriz está ordenada, verifique el valor medio del rango de búsqueda actual, luego, si el valor es menor, verifique el rango inferior, y si el valor es mayor, verifique el rango superior. La clasificación de bloques utiliza dos variantes: una que encuentra la primera posición para insertar un valor en la matriz ordenada y otra que encuentra la última posición.
• Búsqueda lineal : encuentre un valor particular en una matriz verificando cada elemento en orden, hasta que lo encuentre.
• Orden de inserción : para cada elemento de la matriz, realice un bucle hacia atrás y busque dónde debe insertarse, luego insértelo en esa posición.
• Rotación de matriz : mueva los elementos de una matriz hacia la izquierda o hacia la derecha algunos espacios, con valores en los bordes envueltos alrededor del otro lado. Las rotaciones se pueden implementar como tres inversiones .

Rotate(array, amount, range)
    Reverse(array, range)
    Reverse(array, [range.start, range.start + amount))
    Reverse(array, [range.start + amount, range.end))

• Potencia de piso de dos : piso un valor a la siguiente potencia de dos. Por lo tanto, 63 se convierte en 32, 64 permanece 64, y así sucesivamente.

FloorPowerOfTwo(x)
    x = x | (x >> 1)
    x = x | (x >> 2)
    x = x | (x >> 4)
    x = x | (x >> 8)
    x = x | (x >> 16)
    if (this is a 64-bit system)
        x = x | (x >> 32)
    return x - (x >> 1)

Bucle exterior

Como se indicó anteriormente, el bucle exterior de una clasificación de bloque es idéntico a una clasificación de fusión de abajo hacia arriba. Sin embargo, se beneficia de la variante que garantiza que cada subarreglo A y B tenga el mismo tamaño dentro de un elemento:

   BlockSort(array)
       power_of_two = FloorPowerOfTwo(array.size)
       scale = array.size/power_of_two // 1.0 ≤ scale < 2.0
      
       // insertion sort 16–31 items at a time
       for (merge = 0; merge < power_of_two; merge += 16)
           start = merge * scale
           end = start + 16 * scale
           InsertionSort(array, [start, end))
      
       for (length = 16; length < power_of_two; length += length)
           for (merge = 0; merge < power_of_two; merge += length * 2)
               start = merge * scale
               mid = (merge + length) * scale
               end = (merge + length * 2) * scale
              
               if (array[end − 1] < array[start])
                   // the two ranges are in reverse order, so a rotation is enough to merge them
                   Rotate(array, mid − start, [start, end))
               else if (array[mid − 1] > array[mid])
                   Merge(array, A = [start, mid), B = [mid, end))
               // else the ranges are already correctly ordered

También se pueden usar matemáticas de punto fijo , al representar el factor de escala como una fracción integer_part + numerator/denominator:

   power_of_two = FloorPowerOfTwo(array.size)
   denominator = power_of_two/16
   numerator_step = array.size % denominator
   integer_step = floor(array.size/denominator)
  
   // insertion sort 16–31 items at a time
  
   while (integer_step < array.size)
       integer_part = numerator = 0
       while (integer_part < array.size)
           // get the ranges for A and B
           start = integer_part
          
           integer_part += integer_step
           numerator += numerator_step
           if (numerator ≥ denominator)
               numerator −= denominator
               integer_part++
          
           mid = integer_part
          
           integer_part += integer_step
           numerator += numerator_step
           if (numerator ≥ denominator)
               numerator −= denominator
               integer_part++
          
           end = integer_part
          
           if (array[end − 1] < array[start])
               Rotate(array, mid − start, [start, end))
           else if (array[mid − 1] > array[mid])
               Merge(array, A = [start, mid), B = [mid, end))
      
       integer_step += integer_step
       numerator_step += numerator_step
       if (numerator_step ≥ denominator)
           numerator_step −= denominator
           integer_step++

Extraer tampones

El proceso de extracción de búfer para la clasificación de bloques.

Los dos buffers internos necesarios para cada nivel de la etapa de combinación se crean desplazando los primeros 2 √ A instancias de cada valor dentro de un Un subconjunto del 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 principio. Si A no contiene suficientes valores únicos para llenar los dos búferes (de tamaño √ A cada uno), B también se puede usar. 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.

while (integer_step < array.size)
    block_size = √integer_step
    buffer_size = integer_step/block_size + 1
    [extract two buffers of size 'buffer_size' each]

Si B tampoco contiene suficientes valores únicos, extrae la mayor cantidad de valores únicos que pudo encontrar, luego ajusta el tamaño de los bloques A y B de manera que la cantidad de bloques A resultantes sea ​​menor o igual que la cantidad de elementos únicos extraídos del búfer. En este caso, solo se utilizará un búfer; el segundo búfer no existirá.

buffer_size = [number of unique values found]
block_size = integer_step/buffer_size + 1
  
integer_part = numerator = 0
while (integer_part < array.size)
    [get the ranges for A and B]
    [adjust A and B to not include the ranges used by the buffers]

Etiquetar bloques A

Etiquetado de los bloques A utilizando valores del primer búfer interno. Tenga en cuenta que el primer bloque A y el último bloque B tienen un tamaño desigual.

Una vez que se han creado uno o dos búferes internos, comienza a fusionar cada subarreglo A y B para este nivel del tipo de combinación. Para hacerlo, divide cada subarreglo A y B en bloques de tamaño uniforme del tamaño calculado en el paso anterior, donde el primer bloque A y el último bloque B tienen un tamaño desigual si es necesario. Luego 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 búferes internos. Esto se conoce como etiquetar los bloques.

// blockA is the range of the remaining A blocks,
// and firstA is the unevenly sized first A block
blockA = [A.start, A.end)
firstA = [A.start, A.start + |blockA| % block_size)
  
// swap the second value of each A block with the value in buffer1
for (index = 0, indexA = firstA.end + 1; indexA < blockA.end; indexA += block_size)
    Swap(array[buffer1.start + index], array[indexA])
    index++
  
lastA = firstA
blockB = [B.start, B.start + minimum(block_size, |B|))
blockA.start += |firstA|

Rodar y soltar

Dos bloques A rodando por los bloques B. Una vez que el primer bloque A se deja atrás, el bloque A de tamaño desigual se fusiona localmente con los valores B que le siguen.

Después de definir y etiquetar los bloques A de esta manera, los bloques A son laminados a través de los bloques B por el bloque de intercambiar 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 es menor o igual al último valor del bloque B que acaba de intercambiarse 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 rodantes y el valor etiquetado se restaura con su valor original del primer búfer. Esto se conoce como dejar caer un bloque detrás, ya que ya no se lanzará junto con los bloques A restantes. Ese bloque A se inserta luego en el bloque B anterior, primero usando una búsqueda binaria en B para encontrar el índice donde el primer valor de A es menor o igual al valor en ese índice de B, y luego girando A en B en ese índice.

   minA = blockA.start
   indexA = 0
  
   while (true)
       // if there's a previous B block and the first value of the minimum A block is ≤
       // the last value of the previous B block, then drop that minimum A block behind.
       // or if there are no B blocks left then keep dropping the remaining A blocks.
       if ((|lastB| > 0 and array[lastB.end - 1] ≥ array[minA]) or |blockB| = 0)
           // figure out where to split the previous B block, and rotate it at the split
           B_split = BinaryFirst(array, array[minA], lastB)
           B_remaining = lastB.end - B_split
          
           // swap the minimum A block to the beginning of the rolling A blocks
           BlockSwap(array, blockA.start, minA, block_size)
          
           // restore the second value for the A block
           Swap(array[blockA.start + 1], array[buffer1.start + indexA])
           indexA++
          
           // rotate the A block into the previous B block
           Rotate(array, blockA.start - B_split, [B_split, blockA.start + block_size))
          
           // locally merge the previous A block with the B values that follow it,
           // using the second internal buffer as swap space (if it exists)
           if (|buffer2| > 0)
               MergeInternal(array, lastA, [lastA.end, B_split), buffer2)
           else
               MergeInPlace(array, lastA, [lastA.end, B_split))
          
           // update the range for the remaining A blocks,
           // and the range remaining from the B block after it was split
           lastA = [blockA.start - B_remaining, blockA.start - B_remaining + block_size)
           lastB = [lastA.end, lastA.end + B_remaining)
          
           // if there are no more A blocks remaining, this step is finished
           blockA.start = blockA.start + block_size
           if (|blockA| = 0)
               break
          
           minA = [new minimum A block] (see below)
       else if (|blockB| < block_size)
           // move the last B block, which is unevenly sized,
           // to before the remaining A blocks, by using a rotation
           Rotate(array, blockB.start - blockA.start, [blockA.start, blockB.end))
          
           lastB = [blockA.start, blockA.start + |blockB|)
           blockA.start += |blockB|
           blockA.end += |blockB|
           minA += |blockB|
           blockB.end = blockB.start
       else
           // roll the leftmost A block to the end by swapping it with the next B block
           BlockSwap(array, blockA.start, blockB.start, block_size)
           lastB = [blockA.start, blockA.start + block_size)
           if (minA = blockA.start)
               minA = blockA.end
          
           blockA.start += block_size
           blockA.end += block_size
           blockB.start += block_size
          
           // this is equivalent to minimum(blockB.end + block_size, B.end),
           // but that has the potential to overflow
           if (blockB.end > B.end - block_size)
               blockB.end = B.end
           else
               blockB.end += block_size
  
   // merge the last A block with the remaining B values
   if (|buffer2| > 0)
       MergeInternal(array, lastA, [lastA.end, B.end), buffer2)
   else
       MergeInPlace(array, lastA, [lastA.end, B.end))

Una optimización que se puede aplicar durante este paso es la técnica del agujero flotante . Cuando el bloque A mínimo se deja atrás y debe rotarse al 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 para aprovechar el hecho de que el contenido de ese búfer no necesita retener ningún orden. Entonces, en lugar de rotar el segundo búfer (que solía ser el bloque A antes del intercambio de bloque) al bloque B anterior en el índice de posición , los valores en el bloque B después del índice pueden simplemente intercambiarse en bloque con los últimos elementos del búfer.

El agujero flotante en este caso se refiere al contenido del segundo búfer interno que flota alrededor de la matriz y actúa como un agujero en el sentido de que los elementos no necesitan mantener su orden.

Fusiones locales

Una vez que el bloque A se ha rotado en el bloque B, el bloque A anterior se fusiona con los valores B que le 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, significa el primer bloque A, y así sucesivamente.

   MergeInternal(array, A, B, buffer)
       // block swap the values in A with those in 'buffer'
       BlockSwap(array, A.start, buffer.start, |A|)
      
       A_count = 0, B_count = 0, insert = 0
       while (A_count < |A| and B_count < |B|)
           if (array[buffer.start + A_count] ≤ array[B.start + B_count])
               Swap(array[A.start + insert], array[buffer.start + A_count])
               A_count++
           else
               Swap(array[A.start + insert], array[B.start + B_count])
               B_count++
           insert++
      
       // block swap the remaining part of the buffer with the remaining part of the array
       BlockSwap(array, buffer.start + A_count, A.start + insert, |A| - A_count)

Si el segundo búfer no existe, se debe realizar una operación de combinación estrictamente en el lugar, como una versión basada en rotación del algoritmo de Hwang y Lin, el algoritmo de Dudzinski y Dydek, o una búsqueda binaria repetida y rotación.

   MergeInPlace(array, A, B)
       while (|A| > 0 and |B| > 0)
           // find the first place in B where the first item in A needs to be inserted
           mid = BinaryFirst(array, array[A.start], B)
          
           // rotate A into place
           amount = mid - A.end
           Rotate(array, amount, [A.start, mid))
          
           // calculate the new A and B ranges
           B = [mid, B.end)
           A = [A.start + amount, mid)
           A.start = BinaryLast(array, array[A.start], A)

Después de eliminar el bloque A mínimo y fusionar el bloque A anterior con los valores B que le siguen, el nuevo bloque A mínimo debe encontrarse dentro de los bloques que aún se están enrollando en 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 (array[findA + 1] < array[minA + 1])
        minA = findA

Estos bloques A restantes continúan rodando a través de la matriz y se colocan e insertan donde pertenecen. Este proceso se repite hasta que todos los bloques A se han dejado caer y se han rotado al bloque B anterior.

Una vez que el último bloque A restante se ha dejado atrás e insertado en B donde pertenece, debe fusionarse con los valores B restantes que le siguen. Esto completa el proceso de fusión para ese par particular de subarreglos A y B. Sin embargo, debe repetir el proceso para los subarreglos A y B restantes para el nivel actual de la clasificación de combinación.

Tenga en cuenta que los búferes internos se pueden reutilizar para cada conjunto de subarreglos A y B para este nivel de clasificación de combinación, y no es necesario volver a extraerlos ni modificarlos de ninguna manera.

Volver a distribuir

Después de que se hayan fusionado todos los subarreglos A y B, aún quedan uno o dos búferes internos. El primer búfer interno se usó para etiquetar los bloques A, y su contenido todavía está en el mismo orden que antes, pero el segundo búfer interno puede haber tenido su contenido reorganizado cuando se usó como espacio de intercambio para las fusiones. Esto significa que el contenido del segundo búfer deberá ordenarse mediante un algoritmo diferente, como la ordenación por inserción. Luego, los dos búferes deben redistribuirse nuevamente en la matriz utilizando el proceso opuesto que se usó para crearlos.

Después de repetir estos pasos para cada nivel de la clasificación de combinación ascendente, se completa la clasificación de bloques.

Variantes

La clasificación de bloques funciona extrayendo dos búferes internos, dividiendo los subarreglos A y B en bloques de tamaño uniforme, enrollando y soltando los bloques A en B (usando el primer búfer para rastrear el orden de los bloques A), fusionando localmente usando el segundo búfer como intercambio space, 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 clasificación de bloques le permite usar 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 encaje en él. En esta situación, sería idéntico a un tipo de combinación.

Algunas buenas opciones para el tamaño del búfer son:

En lugar de etiquetar los bloques A utilizando el contenido de uno de los búferes internos, se puede usar un búfer de imitación de movimiento indirecto . Este es un búfer interno definido como s1 t s2 , donde s1 y s2 son cada uno tan grande 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 (asegurando así que no el valor en s2 aparece en s1 ). Se sigue utilizando un segundo búfer interno que contiene valores únicos √ A. Los primeros valores √ A de s1 y s2 se intercambian entre sí para codificar información en el búfer 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 por los bloques B. Una vez que se han eliminado todos los bloques A, el búfer de imitación de movimiento se usa para decodificar si un bloque dado en la matriz es un bloque A o un bloque B, cada bloque A se gira a B y se usa el segundo búfer interno como espacio de intercambio para las fusiones locales.

El segundo valor de cada bloque A no necesita necesariamente ser etiquetados - la primera, la última, o cualquier otro elemento se podría utilizar en su lugar. Sin embargo, si el primer valor está etiquetado, los valores deberán leerse desde el primer búfer interno (donde se intercambiaron) al decidir dónde colocar el bloque A mínimo.

Se pueden usar muchos algoritmos de clasificación para clasificar el contenido del segundo búfer interno, incluidos los ordenamientos inestables como el ordenamiento rápido , ya que se garantiza que el contenido del búfer es único. Sin embargo, todavía se recomienda la ordenación por inserción por su rendimiento situacional y la falta de recursividad.

Análisis

La clasificación de bloques es una clase de algoritmos bien definida y comprobable, con implementaciones de trabajo disponibles como combinación y clasificación. Esto permite medir y considerar sus características.

Complejidad

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 O ( n ² ) , por lo que esto conduce a cualquier lugar desde O (16 ² × n / 16) a O (31 ² × n / 31) , que es O ( n ) 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 √ A en tamaño, la operación O ( √ n ² ) también termina siendo O ( n ) .

A continuación, debe extraer dos búferes internos para cada nivel del tipo de combinación. Lo hace iterando sobre los elementos en los subarreglos A y B e incrementando un contador cada vez que cambia el valor, y al encontrar suficientes valores, los rota al comienzo de A o al final de B. En el peor de los casos, esto terminará buscar toda la matriz antes de encontrar √ A valores únicos no contiguos, lo que requiere O ( n ) comparaciones y √ A rotaciones para √ A valores. Esto se resuelve en O ( n + √ n × √ n ) u O ( n ) .

Cuando ninguno de los subarreglos A o B contenía valores únicos de √ A para crear los búferes internos, se realiza una operación de fusión in situ normalmente subóptima en la que realiza búsquedas binarias repetidamente y rota A en B. Sin embargo, la falta conocida de valores únicos dentro de cualquier de los subarreglos establece un límite estricto en el número de búsquedas binarias y rotaciones que se realizarán durante este paso, que nuevamente es √ A elementos rotados hasta √ A veces, u O ( n ) . El tamaño de cada bloque también se ajusta para que sea más pequeño en el caso de que encuentre √ A valores únicos pero no 2 √ A , lo que limita aún más el número de valores únicos contenidos dentro de cualquier bloque A o B.

El etiquetado de los bloques A se realiza √ A veces para cada subarreglo A, luego los bloques A se enrollan y se insertan en los bloques B hasta √ A veces. Las fusiones locales conservan la misma complejidad O ( n ) 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 la nueva iteración de bloques mínima A más de √ A bloquea √ A veces. Y el proceso de redistribución del búfer es idéntico al de extracción del búfer, pero a la inversa, y por lo tanto tiene la misma complejidad O ( n ) .

Después de omitir todos menos la complejidad más alta y considerar que hay niveles de log n en el bucle de fusión externo, esto conduce a una complejidad asintótica final de O ( n log n ) para los casos peores y promedio. En el mejor de los casos, cuando los datos ya están en orden, el paso de combinación realiza n / 16 comparaciones para el primer nivel, luego n / 32 , n / 64 , n / 128 , etc. Esta es una serie matemática bien conocida que se resuelve en O ( n ) .

Memoria

Como la clasificación de bloques no es recursiva y no requiere el uso de asignaciones dinámicas , esto conduce a un espacio constante de pila y montón. Utiliza memoria auxiliar O (1) en un modelo transdicotómico , que acepta que los bits O (log n ) necesarios para realizar un seguimiento de los rangos de A y B no pueden ser mayores que 32 o 64 en 32 o 64 bits. sistemas de computación, respectivamente, y por lo tanto simplifica a O (1) espacio para cualquier arreglo que pueda ser asignado de manera factible.

Estabilidad

Aunque los elementos de la matriz se mueven fuera de orden durante una clasificación de bloque, cada operación es completamente 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 clasificación de 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 clasificación de bloques, esos valores se distribuyen de nuevo 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 rodar 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 al inicio de los bloques A y se restaura su segundo valor. Para cuando se hayan insertado todos los bloques A, los bloques A volverán a estar en orden 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 aseguró que el búfer solo contiene valores únicos, la clasificación del contenido del búfer es suficiente para restaurar su orden estable original.

Adaptabilidad

La ordenación por bloques es una ordenación adaptativa en dos niveles: primero, omite la combinación de los subarreglos A y B que ya están en orden. A continuación, cuando es necesario fusionar A y B y se dividen en bloques de tamaño uniforme, los bloques A solo pasan por B hasta donde sea necesario, y cada bloque solo se fusiona con los valores B inmediatamente posteriores. Cuanto más ordenados estaban los datos originalmente, menos valores de B habrá que fusionar en A.

Ventajas

La clasificación por bloques es una clasificación estable que no requiere memoria adicional, lo que es útil en los casos en que no hay suficiente memoria libre para asignar el búfer O (n). Cuando se usa la variante de búfer externo de clasificación de bloques, puede escalar desde el uso de memoria O (n) a búferes progresivamente más pequeños según sea necesario, y seguirá funcionando de manera eficiente dentro de esas restricciones.

Desventajas

La clasificación por bloques no explota rangos de datos ordenados en un nivel tan fino como otros algoritmos, como Timsort . Solo comprueba 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 un tipo de combinación.

Referencias