Блочная сортировка

Не путать со сжатием с сортировкой блоков .

Блочная сортировка

Блочная сортировка стабильно сортирует числа от 1 до 16. Группы сортировки вставкой по 16, извлекают два внутренних буфера, помечают блоки A (размером √ 16 = 4 каждый), прокручивают блоки A через B , локально объединяют их, сортируют второй буфер и перераспределяют буферы.
Сорт	Алгоритм сортировки
Структура данных	Множество
Худшая производительность	О ( п журнал п )
Лучшая производительность	На ) ​ ​
Средняя производительность	О ( п журнал п )
Наихудшая пространственная сложность	О (1)

Сортировка блоков или сортировка слиянием блоков — это алгоритм сортировки, сочетающий как минимум две слияния операции с сортировкой вставками для достижения O ( n log n ) (см. обозначение Big O ) времени сортировки на месте стабильного . Он получил свое название от наблюдения, что объединение двух отсортированных списков, A и B , эквивалентно разбиению A одинакового размера на блоки , вставке каждого A блока в B по специальным правилам и объединению пар AB .

Один практический алгоритм для слияния O ( n log n ) на месте был предложен Пок-Сон Кимом и Арне Кутцнером в 2008 году.

Обзор

Внешний цикл сортировки блоков идентичен сортировке слиянием снизу вверх , где каждый уровень сортировки объединяет пары подмассивов A и B размером 1, затем 2, затем 4, 8, 16 и т. д. до тех пор, пока оба подмассива вместе не станут самим массивом.

Вместо прямого слияния A и B , как в традиционных методах, алгоритм слияния на основе блоков делит A на дискретные блоки размером √ A (в результате блоков √ A ), получается количество также вставляет каждый блок A в B так, чтобы первое значение каждого блока A было меньше или равно (≤) значению B сразу после него, затем локально объединяет каждый блок A с любыми значениями B между ним и следующим A. блоком

Поскольку для слияний по-прежнему требуется отдельный буфер, достаточно большой для хранения A объединяемого блока , для этой цели зарезервированы две области внутри массива (известные как внутренние буферы ). Таким образом, первые два блока A модифицируются так, чтобы содержать первый экземпляр каждого значения внутри A , при этом исходное содержимое этих блоков сдвигается при необходимости. Остальные блоки A затем вставляются в B и объединяются, используя один из двух буферов в качестве пространства подкачки. Этот процесс приводит к перестановке значений в этом буфере.

После того, как каждый блок A и B каждого подмассива A и B был объединен для этого уровня сортировки слиянием, значения в этом буфере должны быть отсортированы для восстановления их исходного порядка, поэтому необходимо применить сортировку вставкой. Затем значения в буферах перераспределяются на первую отсортированную позицию в массиве. Этот процесс повторяется для каждого уровня внешней сортировки слиянием снизу вверх, после чего массив будет стабильно отсортирован.

Алгоритм

В примерах кода используются следующие операторы:

|	побитовое ИЛИ
>>	сдвиг вправо
%	модуль
++ и +=	приращение
[ х , у )	диапазон от ≥ x и < y
|диапазон|	диапазон.конец – диапазон.начало
массив [я]	i -й элемент массива

Кроме того, сортировка блоков опирается на следующие операции как часть общего алгоритма:

• Обмен : обмен местами двух значений в массиве.
• Обмен блоками : обмен диапазоном значений внутри массива со значениями в другом диапазоне массива.
• Двоичный поиск : если массив отсортирован, проверьте среднее значение текущего диапазона поиска, затем, если значение меньше, проверьте нижний диапазон, а если значение больше, проверьте верхний диапазон. Блочная сортировка использует два варианта: один находит первую позицию для вставки значения в отсортированный массив, а другой находит последнюю позицию.
• Линейный поиск : найдите определенное значение в массиве, проверяя каждый элемент по порядку, пока оно не будет найдено.
• Сортировка вставкой : для каждого элемента массива выполните цикл назад и найдите, куда его нужно вставить, а затем вставьте его в эту позицию.
• Вращение массива : перемещение элементов массива влево или вправо на определенное количество пробелов, при этом значения на краях переносятся на другую сторону. Ротации могут быть реализованы как три разворота .

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

• Минимальная степень двойки : минимальное значение до следующей степени двойки. Таким образом, 63 становится 32, 64 остаётся 64 и так далее.

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)

Внешний цикл

Как говорилось ранее, внешний цикл сортировки блоков идентичен сортировке слиянием снизу вверх. Однако он выигрывает от варианта, который гарантирует, что каждый подмассив A и B имеет одинаковый размер с точностью до одного элемента:

   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

Также можно использовать математику с фиксированной точкой , представляя масштабный коэффициент в виде дроби. integer_part + numerator/denominator:

   BlockSort(array)
       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++

Извлечение буферов

Процесс извлечения буфера для сортировки блоков.

необходимые для каждого уровня шага слияния, создаются путем перемещения первых 2 √ A первых экземпляров их значений внутри подмассива A в начало A. Два внутренних буфера , Сначала он перебирает элементы в A и подсчитывает необходимые ему уникальные значения, затем применяет поворот массива, чтобы переместить эти уникальные значения в начало. Если A не содержит достаточно уникальных значений для заполнения двух буферов (размером √ A каждый), B можно использовать с тем же успехом. В этом случае он перемещает последний экземпляр каждого значения в конец B , при этом эта часть B не включается во время слияний.

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

Если B также не содержит достаточно уникальных значений, он извлекает наибольшее количество уникальных значений, которое может найти, а затем корректирует размер блоков A и B так, чтобы количество полученных блоков A было меньше или равно числу блоков A и B. уникальные элементы, извлеченные из буфера. В этом случае будет использоваться только один буфер – второго буфера не будет.

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]

Отметьте блоки A

Маркировка блоков A с использованием значений из первого внутреннего буфера. Обратите внимание, что первый блок A и последний блок B имеют неодинаковый размер.

После создания одного или двух внутренних буферов начинается объединение каждого подмассива A и B для этого уровня сортировки слиянием. Для этого он делит каждый подмассив A и B на блоки одинакового размера, рассчитанного на предыдущем шаге, причем первый блок A и последний блок B имеют неравномерный размер, если это необходимо. Затем он перебирает каждый из блоков A одинакового размера и заменяет второе значение соответствующим значением из первого из двух внутренних буферов. Это называется маркировкой блоков.

// 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|

Свернуть и бросить

Два блока А проходят через блоки Б. Как только первый блок A отстает, блок A неравномерного размера локально объединяется со значениями B, следующими за ним.

После определения и маркировки блоков A таким образом блоки A прокручиваются через блоки B путем замены первого блока A одинакового размера на следующий блок B. Этот процесс повторяется до тех пор, пока первое значение блока A с наименьшим значением тега не станет меньше или равно последнему значению блока B, который был только что заменен блоком A.

В этот момент минимальный блок A (блок A с наименьшим значением тега) заменяется на начало движущихся блоков A, и тегированное значение восстанавливается с исходным значением из первого буфера. Это называется отбрасыванием блока позади, поскольку он больше не будет катиться вместе с оставшимися блоками A. Затем этот блок A вставляется в предыдущий блок B, сначала с помощью двоичного поиска по B, чтобы найти индекс, в котором первое значение A меньше или равно значению этого индекса B, а затем путем поворота A в B по этому индексу.

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

Одной из оптимизаций, которую можно применить на этом этапе, является метод плавающих отверстий . Когда минимальный блок A отстает и его необходимо повернуть в предыдущий блок B, после чего его содержимое перемещается во второй внутренний буфер для локальных слияний, было бы быстрее заранее переместить блок A в буфер и чтобы воспользоваться тем фактом, что содержимому этого буфера не нужно сохранять какой-либо порядок. Таким образом, вместо того, чтобы вращать второй буфер (который раньше был блоком A до замены блока) в предыдущий блок B в позиции index , значения в блоке B после индекса можно просто поменять местами с последними элементами буфера.

Плавающая дыра в этом случае относится к содержимому второго внутреннего буфера , плавающему вокруг массива и действующему как дыра в том смысле, что элементы не должны сохранять свой порядок.

Локальные слияния

После того как блок A был повернут в блок B, предыдущий блок A объединяется со значениями B, следующими за ним, используя второй буфер в качестве пространства подкачки. Когда первый блок А опускается позади, это относится к блоку А неравномерного размера в начале, когда второй блок А опускается позади, это означает первый блок А и так далее.

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)

Если второй буфер не существует, необходимо выполнить операцию слияния строго на месте, например, основанную на вращении версию алгоритма Хванга и Линя, алгоритм Дудзинского и Дыдека, или повторный бинарный поиск и поворот.

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)

После удаления минимального блока A и объединения предыдущего блока A со значениями B, которые следуют за ним, новый минимальный блок A должен быть найден среди блоков, которые все еще перемещаются по массиву. Это решается путем выполнения линейного поиска по этим блокам A и сравнения значений тегов, чтобы найти наименьший из них.

minA = blockA.start
for (findA = minA + block_size; findA < blockA.end - 1; findA += block_size)
    if (array[findA + 1] < array[minA + 1])
        minA = findA

Эти оставшиеся блоки A затем продолжают перемещаться по массиву, отбрасываются и вставляются туда, где им место. Этот процесс повторяется до тех пор, пока все блоки A не будут перенесены в предыдущий блок B.

Как только последний оставшийся блок A будет отброшен и вставлен в B, где он находится, его следует объединить с оставшимися значениями B, которые следуют за ним. На этом процесс слияния для этой конкретной пары подмассивов A и B завершается. Однако затем он должен повторить процесс для оставшихся подмассивов A и B для текущего уровня сортировки слиянием.

Обратите внимание, что внутренние буферы можно повторно использовать для каждого набора подмассивов A и B на этом уровне сортировки слиянием, и их не нужно повторно извлекать или каким-либо образом изменять.

Перераспределить

После объединения всех подмассивов A и B один или два внутренних буфера все еще остаются. Первый внутренний буфер использовался для маркировки блоков A, и его содержимое все еще находится в том же порядке, что и раньше, но содержимое второго внутреннего буфера могло быть переупорядочено, когда он использовался в качестве пространства подкачки для слияний. Это означает, что содержимое второго буфера необходимо будет отсортировать с использованием другого алгоритма, например сортировки вставками. Затем два буфера необходимо перераспределить обратно в массив, используя процесс, противоположный тому, который использовался для их создания.

После повторения этих шагов для каждого уровня сортировки слиянием снизу вверх сортировка блоков завершается.

Варианты

Сортировка блоков работает путем извлечения двух внутренних буферов, разбиения подмассивов A и B на блоки одинакового размера, перемещения блоков A в B (с использованием первого буфера для отслеживания порядка блоков A), локального слияния с использованием второго буфера в качестве подкачки. пространство, сортировка второго буфера и перераспределение обоих буферов. Хотя шаги не меняются, эти подсистемы могут различаться по своей фактической реализации.

Один из вариантов сортировки блоков позволяет ему использовать любой объем предоставленной ему дополнительной памяти, используя этот внешний буфер для объединения подмассива A или блока A с B всякий раз, когда A помещается в него. В этой ситуации это будет идентично сортировке слиянием.

Хороший выбор размера буфера:

Размер	Примечания
(количество + 1)/2	превращается в полноценную сортировку слиянием, поскольку в нее помещаются все подмассивы A.
√ (счет + 1)/2 + 1	это будет размер блоков A на самом большом уровне слияний, поэтому при сортировке блоков можно пропустить использование внутренних слияний или слияний на месте для чего угодно.
512	буфер фиксированного размера, достаточно большой, чтобы обрабатывать многочисленные слияния на меньших уровнях сортировки слиянием
0	если система не может выделить дополнительную память, ни одна память не работает должным образом

Вместо того, чтобы помечать блоки A, используя содержимое одного из внутренних буферов, буфер косвенной имитации движения . вместо этого можно использовать Это внутренний буфер, определенный как s1 t s2 , где каждый из s1 и s2 равен числу блоков A и B, а t содержит любые значения, следующие сразу за s1 и равные последнему значению s1 (таким образом гарантируя, что ни одно значение в s2 появляется в s1 ). Второй внутренний буфер, содержащий уникальные значения √ A , по-прежнему используется. Затем первые √ A значения s1 и s2 меняются местами друг с другом для кодирования в буфер информации о том, какие блоки являются блоками A, а какие — блоками B. Когда блок A с индексом i заменяется блоком B с индексом j (где первый блок A одинакового размера изначально имеет индекс 0), s1[i] и s1[j] меняются местами с s2[i] и s2[ j], соответственно. Это имитирует перемещение блоков A через B. Уникальные значения во втором буфере используются для определения исходного порядка блоков A при их прохождении через блоки B. После того, как все блоки A удалены, буфер имитации движения используется для декодирования того, является ли данный блок в массиве блоком A или блоком B, каждый блок A поворачивается в B, и используется второй внутренний буфер. как пространство подкачки для локальных слияний.

Второе . значение каждого блока A не обязательно должно быть помечено — вместо него можно использовать первый, последний или любой другой элемент Однако, если первое значение помечено, значения необходимо будет прочитать из первого внутреннего буфера (где они были заменены) при принятии решения о том, куда поместить минимальный блок A.

Для сортировки содержимого второго внутреннего буфера можно использовать множество алгоритмов сортировки, включая нестабильные сортировки, такие как быстрая сортировка , поскольку уникальность содержимого буфера гарантирована. Тем не менее, сортировку вставками по-прежнему рекомендуется из-за ее ситуационной производительности и отсутствия рекурсии.

Реализации

Известные реализации блочной сортировки включают:

• Реализация Куцнера и Кима на C++.
• Wikisort, реализация Майка Макфаддена, основанная на статье Куцнера и Кима.
• GrailSort (и переписанный HolyGrailSort), реализация Андрея Астрелина на основе Хуанга и Лэнгстона (1992), который в конечном итоге описывает очень похожий алгоритм.

Анализ

Блочная сортировка — это четко определенный и тестируемый класс алгоритмов, рабочие реализации которого доступны в виде слияния и сортировки. Это позволяет измерить и учесть его характеристики.

Сложность

Дополнительная информация: обозначение Big O § Порядки общих функций.

Сортировка блоков начинается с выполнения сортировки вставками групп по 16–31 элемент массива. Сортировка вставками – это $O(n^{2})$ операции, так что это приводит к чему угодно от $O(16^{2}\times n/16)$ к $O(31^{2}\times n/31)$, что $O(n)$ если постоянные факторы опущены . Он также должен применить сортировку вставкой ко второму внутреннему буферу после завершения каждого уровня слияния. Однако, поскольку этот буфер был ограничен ${\sqrt {A}}$ по размеру, $O{\sqrt {n}}^{2}$ операция также оказывается $O(n)$.

Затем он должен извлечь два внутренних буфера для каждого уровня сортировки слиянием. Это делается путем перебора элементов в подмассивах A и B и увеличения счетчика при каждом изменении значения, а после нахождения достаточного количества значений он поворачивает их к началу A или концу B. В худшем случае это закончится поиск по всему массиву, прежде чем найти ${\sqrt {A}}$ несмежные уникальные значения, что требует $O(n)$ сравнения и ${\sqrt {A}}$ ротации для ${\sqrt {A}}$ ценности. Это решает $O(n+{\sqrt {n}}\times {\sqrt {n}})$, или $O(n)$.

Когда ни один из подмассивов A или B не содержал ${\sqrt {A}}$ уникальных значений для создания внутренних буферов, обычно выполняется неоптимальная операция слияния на месте, при которой он неоднократно выполняет двоичный поиск и вращает A в B. Однако известное отсутствие уникальных значений в любом из подмассивов накладывает жесткое ограничение на количество бинарный поиск и ротацию, которые будут выполняться на этом этапе, что опять же ${\sqrt {A}}$ элементы повернуты до ${\sqrt {A}}$ раз, или $O(n)$. Размер каждого блока также корректируется так, чтобы он был меньше в том случае, если он найден ${\sqrt {A}}$ уникальные значения, но не 2 ${\sqrt {A}}$, что дополнительно ограничивает количество уникальных значений, содержащихся в любом блоке A или B.

Маркировка блоков А выполняется ${\sqrt {A}}$ раз для каждого подмассива A, затем блоки A прокручиваются и вставляются в блоки B до ${\sqrt {A}}$ раз. Локальные слияния сохраняют то же самое $O(n)$ сложность стандартного слияния, хотя и с большим количеством присваиваний, поскольку значения необходимо менять местами, а не копировать. Линейный поиск нового минимального блока A повторяется ${\sqrt {A}}$ блоки ${\sqrt {A}}$ раз. А процесс перераспределения буфера идентичен извлечению буфера, но в обратном порядке, и поэтому имеет тот же $O(n)$ сложность.

Опустив все, кроме самой высокой сложности , и учитывая, что есть $\log {n}$ уровней во внешнем цикле слияния, это приводит к окончательной асимптотической сложности $O(n\log {n})$ для худшего и среднего случаев. В лучшем случае, когда данные уже в порядке, выполняется шаг слияния. $n/16$ сравнения для первого уровня, затем $n/32$, $n/64$, $n/128$и т. д. Это известный математический ряд , который разрешается как $O(n)$.

Память

Поскольку сортировка блоков является нерекурсивной и не требует использования динамического распределения , это приводит к постоянному стека пространству и кучи. Он использует вспомогательную память O(1) в трансдихотомической модели , которая допускает, что биты O(log n ), необходимые для отслеживания диапазонов для A и B, не могут быть больше 32 или 64 в 32-битной или 64-битной версии. вычислительных систем соответственно и, следовательно, упрощается до O(1) пространства для любого массива, который можно выделить.

Стабильность

Дополнительная информация: Алгоритм сортировки § Стабильность.

Хотя элементы массива во время сортировки блоков перемещаются не по порядку, каждая операция полностью обратима и после ее завершения восстанавливает исходный порядок эквивалентных элементов.

Стабильность требует, чтобы первый экземпляр каждого значения в массиве перед сортировкой оставался первым экземпляром этого значения после сортировки. Сортировка блоков перемещает эти первые экземпляры в начало массива, чтобы создать два внутренних буфера, но когда все слияния завершены для текущего уровня сортировки блоков, эти значения распределяются обратно в первую отсортированную позицию в массиве. Это сохраняет стабильность.

Перед прокруткой блоков A через блоки B второе значение каждого блока A заменяется значением из первого буфера. В этот момент блоки A перемещаются не по порядку, чтобы катиться через блоки B. Однако как только он находит место, где следует вставить наименьший блок A в предыдущий блок B, этот наименьший блок A перемещается обратно в начало блоков A, и его второе значение восстанавливается. К тому времени, как все блоки A будут вставлены, блоки A снова будут в порядке, и первый буфер будет содержать исходные значения в исходном порядке.

Использование второго буфера в качестве пространства подкачки при объединении блока A с некоторыми значениями B приводит к перестановке содержимого этого буфера. Однако, поскольку алгоритм уже гарантирует, что буфер содержит только уникальные значения, сортировки содержимого буфера достаточно, чтобы восстановить их первоначальный стабильный порядок.

Адаптивность

Блочная сортировка — это адаптивная сортировка на двух уровнях: во-первых, она пропускает объединение подмассивов A и B, которые уже находятся в порядке. Затем, когда A и B необходимо объединить и разбить на блоки одинакового размера, блоки A прокручиваются через B только настолько, насколько это необходимо, и каждый блок объединяется только со значениями B, следующими непосредственно за ним. Чем более упорядоченными были исходные данные, тем меньше будет значений B, которые необходимо будет объединить в A.

Преимущества

Блочная сортировка — это стабильная сортировка, не требующая дополнительной памяти, что полезно в тех случаях, когда недостаточно свободной памяти для выделения буфера O(n). При использовании варианта сортировки блоков с внешним буфером он может масштабироваться от использования памяти O (n) до постепенно уменьшающихся буферов по мере необходимости и по-прежнему будет эффективно работать в этих ограничениях.

Недостатки

Блочная сортировка не использует отсортированные диапазоны данных на таком же высоком уровне, как некоторые другие алгоритмы, такие как Timsort . Он проверяет эти отсортированные диапазоны только на двух предопределенных уровнях: подмассивах A и B и блоках A и B. Кроме того, его сложнее реализовать и распараллелить по сравнению с сортировкой слиянием.