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

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

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

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

Блочная сортировка, или блочная сортировка слиянием, также называется викисорт^[1][2], это алгоритм сортировки объединение как минимум двух слияние операции с вставка сортировки прибыть в О(п бревно п) на месте стабильный сортировка. Он получил свое название от наблюдения, что слияние двух отсортированных списков, А и B, эквивалентно нарушению А на равные по размеру блоки, вставляя каждый А блокировать в B по особым правилам, и слияние AB пары.

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

Обзор

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

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

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

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

Алгоритм

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

|	побитовое ИЛИ
>>	сдвиг вправо
%	по модулю
++ и + =	приращение
[Икс, у)	классифицировать от ≥ Икс и < у
| диапазон |	range.end - range.start
массив [я]	я-й пункт массив

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

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

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

• Этаж мощность двух: этаж значение в следующей степени двойки. 63 становится 32, 64 остается 64 и так далее.^[7]

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

Внешняя петля

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

   BlockSort(массив) power_of_two = ЭтажPowerOfTwo(array.size) scale = array.size / power_of_two // 1.0 ≤ масштаб <2.0             // вставка сортирует 16–31 элемент за раз       для (merge = 0; merge InsertionSort(массив, [начало, конец)) для (длина = 16; длина <мощность_два; длина + = длина) для (merge = 0; merge если (массив [конец - 1] <массив [начало]) // два диапазона расположены в обратном порядке, поэтому для их объединения достаточно поворота                   Повернуть(массив, середина - начало, [начало, конец)) иначе если (массив [середина - 1]> массив [середина]) Объединить(массив, A = [начало, середина), B = [середина, конец)) // иначе диапазоны уже правильно упорядочены

Математика с фиксированной точкой также может использоваться, представляя масштабный коэффициент в виде дроби целая_часть + числитель / знаменатель:

   power_of_two = ЭтажPowerOfTwo(array.size) denominator = power_of_two / 16 numerator_step = array.size% denominator integer_step = этаж(размер массива / знаменатель) // вставка сортирует 16–31 элемент за раз     в то время как (integer_step в то время как (целая_часть <размер_массива) // получаем диапазоны для A и B           start = integer_part integer_part + = integer_step числитель + = числитель_шаг если (числитель ≥ знаменатель) числитель - = знаменатель целая_часть ++ mid = целая_часть целая_часть + = целочисленный_шаг числитель + = числитель_шаг если (числитель ≥ знаменатель) числитель - = знаменатель целая_часть ++ конец = целая_часть если (массив [конец - 1] <массив [начало]) Повернуть(массив, середина - начало, [начало, конец)) иначе если (массив [середина - 1]> массив [середина]) Объединить(массив, A = [начало, середина), B = [середина, конец)) integer_step + = integer_step numerator_step + = numerator_step если (шаг_числителя ≥ знаменатель) шаг_числителя - = знаменатель целочисленный_шаг ++

Извлечь буферы

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

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

в то время как (integer_step √integer_step    buffer_size = integer_step / block_size + 1 [извлеките два буфера размером 'buffer_size' каждый]

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

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

Блоки тега A

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

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

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

Катись и падай

Два блока A проходят через блоки B. После того, как первый блок 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 в то время как (истинный) // если есть предыдущий блок B и первое значение минимального блока A ≤       // последнее значение предыдущего блока B, затем отбрасываем этот минимальный блок A.       // или, если не осталось блоков B, продолжаем отбрасывать оставшиеся блоки A.       если ((| lastB |> 0 и массив [lastB.end - 1] ≥ массив [minA]) или | blockB | = 0) // выяснить, где разделить предыдущий блок B, и повернуть его на разделении           B_split = BinaryFirst(массив, массив [minA], lastB) B_remaining = lastB.end - B_split // меняем минимальный блок A на начало прокрутки блоков A           BlockSwap(массив, blockA.start, minA, block_size) // восстанавливаем второе значение для блока A           Замена(массив [blockA.start + 1], массив [buffer1.start + indexA]) indexA ++ // повернуть блок A в предыдущий блок B           Повернуть(массив, blockA.start - B_split, [B_split, blockA.start + block_size)) // локально объединить предыдущий блок A со следующими за ним значениями B,           // использование второго внутреннего буфера в качестве области подкачки (если он существует)           если (| буфер2 |> 0) MergeInternal(массив, lastA, [lastA.end, B_split), buffer2) еще               MergeInPlace(массив, 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, этот шаг завершен           blockA.start = blockA.start + block_size если (| blockA | = 0) перемена                     minA = [новый минимальный блок A] (Смотри ниже)       иначе если (| блокB | <размер_блока) // перемещаем последний блок B, размер которого неравномерен,           // перед остальными блоками A, используя поворот           Повернуть(массив, 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 еще           // прокручиваем крайний левый блок A до конца, заменяя его следующим блоком B           BlockSwap(массив, blockA.start, blockB.start, block_size) lastB = [blockA.start, blockA.start + block_size) если (minA = blockA.start) minA = blockA.end blockA.start + = block_size blockA.end + = block_size blockB.start + = block_size // это эквивалентно минимум(blockB.end + block_size, B.end),           // но это может переполнение           если (blockB.end> B.end - размер_блока) blockB.end = B.end еще               blockB.end + = размер_блока // объединить последний блок A с оставшимися значениями B   если (| буфер2 |> 0) MergeInternal(массив, lastA, [lastA.end, B.end), buffer2) еще       MergeInPlace(массив, lastA, [lastA.end, B.end))

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

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

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

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

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

Если второй буфер не существует, должна быть выполнена операция слияния строго на месте, например, основанная на ротации версия алгоритма Хванга и Линя,^[9][10] алгоритм Дудзинского и Дидека,^[11] или повторный бинарный поиск и поворот.

   MergeInPlace(массив, A, B) в то время как (| A |> 0 и | B | > 0) // находим первое место в B, куда нужно вставить первый элемент в A           mid = BinaryFirst(массив, массив [A.start], B) // повернуть A на место           amount = mid - A.end Повернуть(массив, сумма, [начало, середина)) // вычисляем новые диапазоны A и B           B = [mid, B.end) A = [A.start + amount, mid) A.start = BinaryLast(массив, массив [A.start], A)

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

minA = blockA.startдля (findA = minA + block_size; findA если (массив [findA + 1] 
Эти оставшиеся блоки A затем продолжают перемещаться по массиву, отбрасываются и вставляются туда, где они принадлежат. Этот процесс повторяется до тех пор, пока все блоки A не будут отброшены и повернуты в предыдущий блок B.
После того, как последний оставшийся блок A был отброшен и вставлен в B, где он принадлежит, его следует объединить с оставшимися значениями B, которые следуют за ним. Это завершает процесс слияния для конкретной пары подмассивов A и B. Однако затем он должен повторить процесс для оставшихся подмассивов A и B для текущего уровня сортировки слиянием.
Обратите внимание, что внутренние буферы можно повторно использовать для каждого набора подмассивов A и B для этого уровня сортировки слиянием, и их не нужно повторно извлекать или изменять каким-либо образом.
Распространять
После объединения всех подмассивов A и B один или два внутренних буфера все еще остаются. Первый внутренний буфер использовался для маркировки блоков A, и его содержимое все еще находится в том же порядке, что и раньше, но во втором внутреннем буфере, возможно, было переупорядочено его содержимое, когда оно использовалось в качестве пространства подкачки для слияний. Это означает, что содержимое второго буфера необходимо будет отсортировать с использованием другого алгоритма, например сортировки вставкой. Затем два буфера необходимо перераспределить обратно в массив, используя противоположный процесс, который использовался для их создания.
После повторения этих шагов для каждого уровня сортировки слияния снизу вверх сортировка блоков завершается.
Варианты









Сортировка блоков работает путем извлечения двух внутренних буферов, разделения подмассивов A и B на блоки равного размера, перекатывания и отбрасывания блоков A в B (с использованием первого буфера для отслеживания порядка блоков A), локального слияния с использованием второго буфера в качестве подкачки пространство, сортировка второго буфера и перераспределение обоих буферов. Хотя шаги не меняются, эти подсистемы могут различаться по своей фактической реализации.
Один из вариантов сортировки блоков позволяет ему использовать любой объем дополнительной памяти, предоставленной ему, с помощью этого внешний буфер для слияния подмассива A или блока A с B всякий раз, когда A вписывается в него. В этой ситуации это было бы идентично сортировке слиянием.
Хороший выбор размера буфера:
Размер
Заметки
(count + 1) / 2
превращается в сортировку слиянием на полной скорости, поскольку в нее вписываются все подмассивы A
√(count + 1) / 2 + 1
это будет размер блоков A на самом большом уровне слияний, поэтому сортировку блоков можно пропустить с использованием внутренних или локальных слияний для чего угодно
512
буфер фиксированного размера, достаточно большой для обработки многочисленных слияний на меньших уровнях сортировки слияния
0
если система не может выделить дополнительную память, память не работает нормально
Вместо того, чтобы маркировать блоки A с использованием содержимого одного из внутренних буферов, косвенный буфер имитации движения можно использовать вместо этого.[3][12] Это внутренний буфер, определенный как s1 t s2, где s1 и s2 равны количеству блоков A и B, и т содержит любые значения сразу после s1 которые равны последнему значению s1 (таким образом гарантируя, что s2 появляется в s1). Второй внутренний буфер, содержащий √А уникальные значения все еще используются. Первый √А ценности s1 и s2 затем меняются местами друг с другом для кодирования в буфер информации о том, какие блоки являются блоками A, а какие - блоками B. Когда блок A по индексу я заменяется блоком B по индексу j (где первый блок A одинакового размера изначально имеет индекс 0), s1 [i] и s1 [j] меняются местами на s2 [i] и s2 [j] соответственно. Эта имитирует движения блоков от A до B. Уникальные значения во втором буфере используются для определения исходного порядка блоков A при их прокрутке через блоки B. После того, как все блоки A были отброшены, буфер имитации движения используется для декодирования того, является ли данный блок в массиве блоком A или блоком B, каждый блок A превращается в блок B, и используется второй внутренний буфер в качестве места подкачки для локальных слияний.
В второй значение каждого блока A не обязательно должно быть помечено - вместо него можно использовать первый, последний или любой другой элемент. Однако, если первое значение помечено, значения должны быть прочитаны из первого внутреннего буфера (где они были поменяны местами) при принятии решения о том, где отбросить минимальный блок A.
Для сортировки содержимого второго внутреннего буфера можно использовать множество алгоритмов сортировки, включая нестабильные сортировки, например быстрая сортировка, так как содержимое буфера гарантированно уникально. Тем не менее, сортировка вставкой по-прежнему рекомендуется из-за ее ситуативной производительности и отсутствия рекурсии.
Анализ









Блочная сортировка - это четко определенный и проверяемый класс алгоритмов с рабочими реализациями, доступными в виде слияния и сортировки.[13][14][15] Это позволяет измерять и учитывать его характеристики.
Сложность
Блочная сортировка начинается с сортировки вставкой групп из 16–31 элемента в массиве. Сортировка вставкой - это О (п2) операции, поэтому это приводит к любому из О(162 × п/16) к О(312 × п/31), который О(п) однажды постоянные коэффициенты опускаются. Он также должен применять сортировку вставкой во втором внутреннем буфере после завершения каждого уровня слияния. Однако, поскольку этот буфер был ограничен √А по размеру О(√п2) операция также заканчивается О(п).
Затем он должен извлечь два внутренних буфера для каждого уровня сортировки слиянием. Он делает это, перебирая элементы в подмассивах A и B и увеличивая счетчик всякий раз, когда значение изменяется, и после нахождения достаточного количества значений он поворачивает их к началу A или концу B. В худшем случае это закончится поиск по всему массиву перед нахождением √А несмежные уникальные значения, что требует О(п) сравнения и √А ротации для √А ценности. Это решает О(п + √п × √п), или О(п).
Когда ни один из подмассивов A или B не содержал √А уникальных значений для создания внутренних буферов, обычно выполняется неоптимальная операция слияния на месте, когда выполняется многократный двоичный поиск и преобразование A в B. Однако известное отсутствие уникальных значений в любом из подмассивов накладывает жесткое ограничение на количество бинарные поиски и вращения, которые будут выполняться на этом шаге, который снова √А элементы повернуты до √А раз, или О(п). Размер каждого блока также корректируется, чтобы он был меньше в том случае, если он обнаружен. √А уникальные значения, но не 2√А, что дополнительно ограничивает количество уникальных значений, содержащихся в любом блоке A или B.
Пометка блоков A выполняется √А раз для каждого подмассива A, затем блоки A прокручиваются и вставляются в блоки B до √А раз. Локальные слияния сохраняют то же самое О(п) сложность стандартного слияния, хотя и с большим количеством присваиваний, поскольку значения нужно менять местами, а не копировать. Линейный поиск для нахождения нового минимума блока A повторяется √А блоки √А раз. И процесс перераспределения буфера идентичен извлечению буфера, но в обратном порядке, и поэтому имеет то же О(п) сложность.
После исключая все, кроме высшей сложности и учитывая, что есть журнал n уровней во внешнем цикле слияния, это приводит к окончательной асимптотической сложности О(п бревно п) для худшего и среднего случаев. В лучшем случае, когда данные уже в порядке, этап слияния выполняет п/16 сравнения для первого уровня, затем п/32, п/64, п/128и т. д. Это известный математический ряд который решает О(п).
объем памяти
Поскольку сортировка блоков нерекурсивный и не требует использования динамическое размещение, это приводит к постоянному стек и пространство кучи. Он использует вспомогательную память O (1) в трансдихотомическая модель, который принимает, что O (log п) битов, необходимых для отслеживания диапазонов для 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) до постепенно уменьшающихся буферов по мере необходимости, и по-прежнему будет эффективно работать в рамках этих ограничений.
Недостатки









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









 «Блочная сортировка слиянием (WikiSort)»
 Тим Питерс. "Re: WikiSort". Получено 2020-09-13.
 Куцнер, Арне; Ким, Пок-Сон (2008). Стабильное слияние на месте на основе соотношения (PDF). Конспект лекций по информатике. 4978. Springer Berlin Heidelberg. стр. 246–257. Получено 2016-09-07.
 Маннила, Хейкки; Укконен, Эско (14 мая 1984 г.). «Простой линейный алгоритм времени для слияния на месте». Письма об обработке информации. 18 (4): 203–208. Дои:10.1016/0020-0190(84)90112-1.
 Кронрод, М. Александр (февраль 1969 г.). "Оптимальный алгоритм упорядочения без рабочего поля" [Оптимальный алгоритм упорядочивания без области действия]. Известия АН СССР. (на русском). 186 (6): 1256–1258.
 Бентли, Джон (2006). Жемчуг программирования (2-е изд.).
 Уоррен-младший, Генри С. (2013) [2002]. Хакерское наслаждение (2-е изд.). Эддисон Уэсли - Pearson Education, Inc. ISBN  978-0-321-84268-8. 0-321-84268-5.
 Пардо, Луис Трабб (1977). Стабильная сортировка и слияние с оптимальными пространственными и временными границами. SIAM Журнал по вычислениям. 6. С. 351–372.
 Гефферт, Вильям; Катаянен, Джикри; Пасанен, Томи (апрель 2000 г.). «Асимптотически эффективное слияние на месте». Теоретическая информатика. 237 (1–2): 159–181. CiteSeerX  10.1.1.22.5750. Дои:10.1016 / S0304-3975 (98) 00162-5.
 Hwang, F.K .; Лин, С. (1972). Простой алгоритм слияния двух непересекающихся линейно упорядоченных множеств. SIAM Журнал по вычислениям. 1. С. 31–39. Дои:10.1137/0201004. ISSN  0097-5397.
 Дудзинский, Кшиштоф; Дыдек, Анджей (1981). Об алгоритме слияния стабильного хранилища. Письма об обработке информации. 12. С. 5–8.
 Симвонис, Антониос (1995). «Оптимальное стабильное слияние». Компьютерный журнал. 38 (8): 681–690. CiteSeerX  10.1.1.55.6058. Дои:10.1093 / comjnl / 38.8.681.
 Арне Куцнер. «Инструмент для тестирования алгоритмов слияния на месте». Архивировано из оригинал на 2014-04-15. Получено 2014-03-23.
 Арне Куцнер. «Инструмент для тестирования алгоритмов слияния на месте». Архивировано из оригинал на 2016-12-20. Получено 2016-12-11.
 «Реализации блочной сортировки в общественном достоянии для C, C ++ и Java». Получено 2014-03-23.