Сортировка блоков

Сортировка блоков

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

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

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

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

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

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

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

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

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

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

Повернуть (массив, количество, диапазон) Обратить (массив, диапазон) Обратить (массив, [диапазон.начало, диапазон.начало + количество)) Обратить (массив, [диапазон.начало + количество, диапазон.конец))

• Степень пола двойки : возвести значение в степень двойки. Таким образом, 63 становится 32, 64 остается 64 и т. д. ^[5]

FloorPowerOfTwo (x) х = х | (х >> 1) х = х | (х >> 2) х = х | (х >> 4) х = х | (х >> 8) х = х | (х >> 16) если (это 64-битная система) х = х | (х >> 32) вернуть х - (х >> 1)

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

 Блочная сортировка (массив) мощность_двух = ПолМощностиДвух (массив.размер) масштаб = массив.размер/степень_двойки // 1.0 ≤ масштаб < 2.0  // сортировка вставкой 16–31 элементов за раз  для (merge = 0; merge < power_of_two; merge += 16) начало = слияние * масштаб конец = начало + 16 * масштаб ВставкаСортировка (массив, [начало, конец))  для (длина = 16; длина < степень_двойки; длина += длина) для (слияние = 0; слияние < степень_двойки; слияние += длина * 2) начало = слияние * масштаб середина = (объединение + длина) * масштаб конец = (слияние + длина * 2) * масштаб  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_part + numerator/denominator:

 Блочная сортировка (массив) мощность_двух = ПолМощностиДвух (массив.размер) знаменатель = степень_двух/16 numerator_step = array.size % знаменатель integer_step = floor (размер.массива/знаменатель)  // сортировка вставкой 16–31 элементов за раз  в то время как (integer_step < array.size) целая_часть = числитель = 0 while (integer_part < array.size) // получить диапазоны для A и B начало = целая_часть  целая_часть += целая_часть числитель += числитель_шаг если (числитель ≥ знаменатель) числитель −= знаменатель целая_часть++  середина = целая_часть  целая_часть += целая_часть числитель += числитель_шаг если (числитель ≥ знаменатель) числитель −= знаменатель целая_часть++  конец = целая_часть  если (array[end − 1] < array[start]) Повернуть (array, mid − start, [start, end)) иначе если (array[mid − 1] > array[mid]) Объединить (array, A = [start, mid), B = [mid, end))  целочисленный_шаг += целочисленный_шаг шаг_числителя += шаг_числителя если (числитель_шаг ≥ знаменатель) числитель_шаг −= знаменатель целое число_шаг++

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

в то время как (integer_step < array.size) размер_блока = √ целочисленный_шаг размер_буфера = целочисленный_шаг/размер_блока + 1 [извлечь два буфера размером 'buffer_size' каждый]

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

buffer_size = [количество найденных уникальных значений]размер_блока = целочисленный_шаг/размер_буфера + 1 целая_часть = числитель = 0while (integer_part < array.size) [получить диапазоны для A и B]  [изменить A и B так, чтобы они не включали диапазоны, используемые буферами]

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

// blockA — это диапазон оставшихся блоков A, // а firstA — это первый блок A неравного размераблокA = [A.начало, A.конец)firstA = [A.start, A.start + |blockA| % block_size) // поменять местами второе значение каждого блока A со значением в buffer1 for (index = 0, indexA = firstA.end + 1; indexA < blockA.end; indexA += block_size) Swap (array[buffer1.start + index], array[indexA]) индекс++ последнийА = первыйАблокB = [B.старт, B.старт + минимум (размер_блока, |B|))блокA.start += |firstA|

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

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

 minA = blockA.start индексA = 0  while (true) // если есть предыдущий блок B и первое значение минимального блока A ≤  // последнего значения предыдущего блока B, то отбрасываем этот минимальный блок A позади.  // или если не осталось блоков B, то продолжаем отбрасывать оставшиеся блоки A.  if ((|lastB| > 0 and array[lastB.end - 1] ≥ array[minA]) or |blockB| = 0) // выясняем, где разделить предыдущий блок B, и вращаем его в точке разделения B_split = BinaryFirst (array, array[minA], lastB) B_оставшийся = последнийB.конец - B_разделить  // поменять минимальный блок A на начало движущихся блоков A  BlockSwap (array, blockA.start, minA, block_size)  // восстановить второе значение для блока A  Swap (array[blockA.start + 1], array[buffer1.start + indexA]) индексA++  // повернуть блок A в предыдущий блок B  Rotate (array, blockA.start - B_split, [B_split, blockA.start + block_size))  // локально объединить предыдущий блок A со значениями B, которые следуют за ним,  // используя второй внутренний буфер в качестве пространства подкачки (если он существует)  if (|buffer2| > 0) MergeInternal (array, lastA, [lastA.end, B_split), buffer2) else  MergeInPlace (array, lastA, [lastA.end, B_split))  // обновить диапазон для оставшихся блоков A,  // и диапазон, оставшийся от блока B после его разделения lastA = [blockA.start - B_remaining, blockA.start - B_remaining + block_size) LastB = [lastA.end, LastA.end + B_remaining)  // если больше не осталось блоков A, этот шаг завершен блокA.start = блокA.start + размер_блока если (|blockA| = 0) перерыв  minA = [новый минимальный блок A]  (см. ниже)  else if (|blockB| < block_size) // переместить последний блок B, который имеет неравномерный размер,  // перед оставшимися блоками A, используя поворот  Rotate (array, blockB.start - blockA.start, [blockA.start, blockB.end))  LastB = [blockA.start, blockA.start + |blockB|) блокA.start += |блокB| блокA.end += |блокB| minA += |блокB| блокБ.конец = блокБ.начало else  // переместить самый левый блок A в конец, поменяв его местами со следующим блоком B  BlockSwap (array, blockA.start, blockB.start, block_size) LastB = [blockA.start, blockA.start + размер_блока) если (minA = blockA.start) minA = blockA.end  блокA.start += размер_блока blockA.end += размер_блока blockB.start += размер_блока  // это эквивалентно минимуму (blockB.end + block_size, B.end),  // но есть вероятность переполнения  , если (blockB.end > B.end - block_size) блокБ.конец = Б.конец еще blockB.end += размер_блока  // объединить последний блок A с оставшимися значениями B  if (|buffer2| > 0) MergeInternal (array, lastA, [lastA.end, B.end), buffer2) else  MergeInPlace (array, lastA, [lastA.end, B.end))

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

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

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

MergeInternal (array, A, B, buffer) // блокирует обмен значениями в A со значениями в 'buffer'  BlockSwap (array, A.start, buffer.start, |A|) A_count = 0, B_count = 0, вставка = 0 while (A_count < |A| и B_count < |B|) if (array[buffer.start + A_count] ≤ array[B.start + B_count]) Поменять местами (array[A.start + insert], array[buffer.start + A_count]) A_count++ иначе  Поменять местами (массив[A.start + insert], массив[B.start + B_count]) B_count++ вставить++ // блок меняем местами оставшуюся часть буфера с оставшейся частью массива  BlockSwap (array, buffer.start + A_count, A.start + insert, |A| - A_count)

Если второй буфер не существует, необходимо выполнить операцию слияния строго на месте, например, основанную на вращении версию алгоритма Хванга и Линя ^{[7] [8],} алгоритма Дудзинского и Дайдека ^[9] или повторный двоичный поиск и вращение.

MergeInPlace (array, A, B) while (|A| > 0 и |B| > 0) // найти первое место в B, куда нужно вставить первый элемент в A mid = BinaryFirst (array, array[A.start], B) // повернуть A на место сумма = середина - конец А Поворот (массив, количество, [A.start, mid)) // вычислить новые диапазоны A и B B = [середина, B.конец) A = [A.начало + сумма, середина) A.start = BinaryLast (массив, массив[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 = найтиA

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

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

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

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

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

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

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

Хорошие варианты размера буфера включают:

Вместо того, чтобы помечать блоки A с помощью содержимого одного из внутренних буферов, можно использовать буфер косвенной имитации движения . ^{[1] [10]} Это внутренний буфер, определяемый как 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++. ^[11]
• Wikisort, реализация Майка Макфаддена, основанная на статье Кутцнера и Кима. ^[12]
• GrailSort (и переписанный HolyGrailSort), реализация Андрея Астрелина, основанная на Хуанге и Лэнгстоне (1992), ^[13] которая в конечном итоге описывает очень похожий алгоритм. ^[14]

Блочная сортировка — это четко определенный и проверяемый класс алгоритмов, рабочие реализации которого доступны как в виде слияния, так и в виде сортировки. ^{[11] [15] [12]} Это позволяет измерять и учитывать его характеристики.

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

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

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

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

После исключения всех, кроме самой высокой сложности , и с учетом того, что во внешнем цикле слияния есть 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 . ^[16] Она проверяет эти отсортированные диапазоны только на двух предопределенных уровнях: подмассивы A и B и блоки A и B. Ее также сложнее реализовать и распараллелить по сравнению с сортировкой слиянием.