View source for Block sort

{{Short description|Efficient sorting algorithm that combines insert and merge operations}}
{{Distinguish|Block-sorting compression}}
{{Infobox Algorithm
|image=[[File:Block sort with numbers 1 to 16 (thumb).gif|link=File:Block_sort_with_numbers_1_to_16.gif|border]]
|caption=Block sort stably sorting numbers 1 to 16.<br />Insertion sort groups of 16, extract two internal buffers, tag the {{mvar|A}} blocks (of size {{math|1={{sqrt|16}} = 4}} each), roll the {{mvar|A}} blocks through {{mvar|B}}, locally merge them, sort the second buffer, and redistribute the buffers.
|class=[[Sorting algorithm]]
|data=[[Array data structure|Array]]
|time={{math|''O''(''n'' log ''n'')}}
|best-time={{math|''O''(''n'')}}
|average-time={{math|''O''(''n'' log ''n'')}}
|space={{math|''O''(1)}}}}

'''Block sort''', or '''block merge sort''', is a [[sorting algorithm]] combining at least two [[merge algorithm|merge]] operations with an [[insertion sort]] to arrive at {{math|''O''(''n'' log ''n'')}} (see [[Big O notation]]) [[in-place]] [[sorting algorithm#Stability|stable]] sorting time. It gets its name from the observation that merging two sorted lists, {{mvar|A}} and {{mvar|B}}, is equivalent to breaking {{mvar|A}} into evenly sized ''blocks'', inserting each {{mvar|A}} block into {{mvar|B}} under special rules, and merging {{mvar|AB}} pairs.

One practical algorithm for {{math|''O''(''n'' log ''n'')}} in-place merging was proposed by Pok-Son Kim and Arne Kutzner in 2008.<ref name="kim2008">{{cite book|last1=Kutzner|first1=Arne|last2=Kim|first2=Pok-Son|year=2008|publisher=Springer Berlin Heidelberg|title=Ratio Based Stable In-Place Merging|series=[[Lecture Notes in Computer Science]]|volume=4978|pages=246–257|url=http://itbe.hanyang.ac.kr/ak/papers/tamc2008.pdf|accessdate=2016-09-07}}</ref>

== Overview ==
The outer loop of block sort is identical to a [[Merge sort#Bottom-up implementation|bottom-up merge sort]], where each ''level'' of the sort merges pairs of subarrays, {{mvar|A}} and {{mvar|B}}, in sizes of 1, then 2, then 4, 8, 16, and so on, until both subarrays combined are the array itself.

Rather than merging {{mvar|A}} and {{mvar|B}} directly as with traditional methods, a block-based merge algorithm divides {{mvar|A}} into discrete blocks of size {{math|{{sqrt|''A''}}}} (resulting in {{math|{{sqrt|''A''}}}} ''number'' of blocks as well),<ref name="mannilla">{{cite journal|last1=Mannila|first1=Heikki|last2=Ukkonen|first2=Esko|title=A Simple Linear Time Algorithm for In-Situ Merging|journal=[[Information Processing Letters]]|volume=18|issue=4|date=14 May 1984|pages=203–208|doi=10.1016/0020-0190(84)90112-1}}</ref> inserts each {{mvar|A}} block into {{mvar|B}} such that the first value of each {{mvar|A}} block is less than or equal (≤) to the {{mvar|B}} value immediately after it, then ''locally merges'' each {{mvar|A}} block with any {{mvar|B}} values between it and the next {{mvar|A}} block.

As merges still require a separate buffer large enough to hold the {{mvar|A}} block to be merged, two areas within the array are reserved for this purpose (known as ''internal buffers'').<ref name="kronrod">{{cite journal|last=Kronrod|first=M. Alexander|date=February 1969|title=Оптимальный алгоритм упорядочения без рабочего поля|trans-title=An Optimal Ordering Algorithm without a Field of Operation|journal=[[Proceedings of the USSR Academy of Sciences]]|volume=186|issue=6|pages=1256–1258|language=ru|url=http://mi.mathnet.ru/eng/dan34705}}</ref> The first two {{mvar|A}} blocks are thus modified to contain the first instance of each value within {{mvar|A}}, with the original contents of those blocks shifted over if necessary. The remaining {{mvar|A}} blocks are then inserted into {{mvar|B}} and merged using one of the two buffers as swap space. This process causes the values in that buffer to be rearranged.

Once every {{mvar|A}} and {{mvar|B}} block of every {{mvar|A}} and {{mvar|B}} subarray have been merged for that level of the merge sort, the values in that buffer must be sorted to restore their original order, so an insertion sort must be applied. The values in the buffers are then redistributed to their first sorted position within the array. This process repeats for each level of the outer bottom-up merge sort, at which point the array will have been stably sorted.

== Algorithm ==
The following operators are used in the code examples:
{| class="wikitable"
|-
! {{pipe}}
| [[Bitwise operation#OR|bitwise OR]]
|-
! >>
| [[Bitwise operation#Logical shift|shift right]]
|-
! %
| [[Modulo operation|modulo]]
|-
! ++ and +=
| [[Increment and decrement operators|increment]]
|-
! [''x'', ''y'')
| [[Interval (mathematics)#Including or excluding endpoints|range]] from ≥ ''x'' and &lt; ''y''
|-
! {{pipe}}range{{pipe}}
| range.end – range.start
|-
! array[i]
| ''i''-th item of ''array''
|}

Additionally, block sort relies on the following operations as part of its overall algorithm:
* '''[[Swap (computer science)|Swap]]''': exchange the positions of two values in an array.
* '''[[Block swap algorithms|Block swap]]''': exchange a range of values within an array with values in a different range of the array.
* '''[[Binary search algorithm|Binary search]]''': assuming the array is sorted, check the middle value of the current search range, then if the value is lesser check the lower range, and if the value is greater check the upper range. Block sort uses two variants: one which finds the ''first'' position to insert a value in the sorted array, and one which finds the ''last'' position.
* '''[[Linear search]]''': find a particular value in an array by checking every single element in order, until it is found.
* '''[[Insertion sort]]''': for each item in the array, loop backward and find where it needs to be inserted, then insert it at that position.
* '''Array rotation''': move the items in an array to the left or right by some number of spaces, with values on the edges wrapping around to the other side. Rotations can be implemented as three [[In-place algorithm#Examples|reversals]].<ref>{{cite book|last=Bentley|first=Jon|title=Programming Pearls|edition=2nd|year=2006|title-link=Programming Pearls}}</ref>

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

* '''Floor power of two''': [[Floor and ceiling functions|floor]] a value to the next power of two. Thus 63 becomes 32, 64 stays 64, and so forth.<ref name="Warren_2013">{{Cite book |title=Hacker's Delight |title-link=Hacker's Delight |first=Henry S. |last=Warren Jr. |date=2013 |orig-year=2002 |edition=2 |publisher=[[Addison Wesley]] - [[Pearson Education, Inc.]] |isbn=978-0-321-84268-8 |id=0-321-84268-5}}</ref>

 '''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 computing|64-bit]] system)
         x = x | (x >> 32)
     return x - (x >> 1)

=== Outer loop ===
As previously stated, the outer loop of a block sort is identical to a bottom-up merge sort. However, it benefits from the variant that ensures each {{var|A}} and {{var|B}} subarray are the same size to within one item:

    '''BlockSort'''(array)
        power_of_two = '''FloorPowerOfTwo'''(array.size)
        scale = array.size/power_of_two <span style="color:green;">// 1.0 ≤ scale < 2.0</span>
       
        <span style="color:green;">// insertion sort 16–31 items at a time</span>
        '''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])
                    <span style="color:green;">// the two ranges are in reverse order, so a rotation is enough to merge them</span>
                    '''Rotate'''(array, mid − start, [start, end))
                '''else if''' (array[mid − 1] > array[mid])
                    '''Merge'''(array, A = [start, mid), B = [mid, end))
                <span style="color:green;">// else the ranges are already correctly ordered</span>

[[Fixed-point arithmetic|Fixed-point math]] may also be used, by representing the scale factor as a fraction <code>integer_part + numerator/denominator</code>:

    '''BlockSort'''(array)
        power_of_two = '''FloorPowerOfTwo'''(array.size)
        denominator = power_of_two/16
        numerator_step = array.size % denominator
        integer_step = '''floor'''(array.size/denominator)
    
        <span style="color:green;">// insertion sort 16&ndash;31 items at a time</span>
    
        '''while''' (integer_step < array.size)
            integer_part = numerator = 0
            '''while''' (integer_part < array.size)
                <span style="color:green;">// get the ranges for A and B</span>
                start = integer_part
            
                integer_part += integer_step
                numerator += numerator_step
                '''if''' (numerator ≥ denominator)
                    numerator &minus;= 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++

=== Extract buffers ===
[[File:Buffer extraction for block sort.gif|thumb|right|The buffer extraction process for block sort.]]

The two internal buffers needed for each level of the merge step are created by moving the first 2{{sqrt|A}} first instances of their values within an {{var|A}} subarray to the start of {{var|A}}. First it iterates over the elements in {{var|A}} and counts off the unique values it needs, then it applies array rotations to move those unique values to the start.<ref name="pardo">{{cite book|last=Pardo|first=Luis Trabb|title=Stable Sorting and Merging with Optimal Space and Time Bounds|series=[[SIAM Journal on Computing]]|volume=6|year=1977|pages=351–372}}</ref> If A did not contain enough unique values to fill the two buffers (of size {{sqrt|A}} each), {{var|B}} can be used just as well. In this case it moves the ''last'' instance of each value to the ''end'' of {{var|B}}, with that part of {{var|B}} not being included during the merges.

 '''while''' (integer_step < array.size)
     block_size = {{sqrt|integer_step}}
     buffer_size = integer_step/block_size + 1
     <span style="color:green;">[extract two buffers of size 'buffer_size' each]</span>

If {{var|B}} does not contain enough unique values either, it pulls out the largest number of unique values it ''could'' find, then adjusts the size of the {{var|A}} and {{var|B}} blocks such that the number of resulting {{var|A}} blocks is less than or equal to the number of unique items pulled out for the buffer. Only one buffer will be used in this case – the second buffer won't exist.

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

=== Tag A blocks ===
[[File:Block sort tagging A blocks.gif|thumb|right|Tagging the {{var|A}} blocks using values from the first internal buffer. Note that the first {{var|A}} block and last {{var|B}} block are unevenly sized.]]
Once the one or two internal buffers have been created, it begins merging each {{var|A}} and {{var|B}} subarray for this level of the merge sort. To do so, it divides each A and B subarray into evenly sized blocks of the size calculated in the previous step, where the first {{var|A}} block and last {{var|B}} block are unevenly sized if needed. It then loops over each of the evenly sized A blocks and swaps the second value with a corresponding value from the first of the two internal buffers. This is known as ''tagging'' the blocks.

 <span style="color:green;">// blockA is the range of the remaining A blocks,</span>
 <span style="color:green;">// and firstA is the unevenly sized first A block</span>
 blockA = [A.start, A.end)
 firstA = [A.start, A.start + |blockA| % block_size)
   
 <span style="color:green;">// swap the second value of each A block with the value in buffer1</span>
 '''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|

=== Roll and drop ===
[[File:Block sort roll and drop.gif|thumb|right|Two A blocks rolling through the B blocks. Once the first A block is dropped behind, the unevenly sized A block is locally merged with the B values that follow it.]]
After defining and tagging the A blocks in this manner, the A blocks are ''rolled'' through the B blocks by block swapping the first evenly sized A block with the next B block. This process repeats until the first value of the A block with the smallest tag value is less than or equal to the last value of the B block that was just swapped with an A block.

At that point, the minimum A block (the A block with the smallest tag value) is swapped to the start of the rolling A blocks and the tagged value is restored with its original value from the first buffer. This is known as ''dropping'' a block behind, as it will no longer be rolled along with the remaining A blocks. That A block is then inserted into the previous B block, first by using a binary search on B to find the index where the first value of A is less than or equal to the value at that index of B, and then by rotating A into B at that index.

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

One optimization that can be applied during this step is the ''floating-hole technique''.<ref name="geffert">{{cite journal |last1=Geffert |first1=Viliam |last2=Katajainen |first2=Jykri |last3=Pasanen |first3=Tomi |title=Asymptotically efficient in-place merging |journal=[[Theoretical Computer Science (journal)|Theoretical Computer Science]] |volume=237 |issue=1–2 |date=April 2000 |pages=159–181 |doi=10.1016/S0304-3975(98)00162-5 |citeseerx=10.1.1.22.5750 }}</ref> When the minimum A block is dropped behind and needs to be rotated into the previous B block, after which its contents are swapped into the second internal buffer for the local merges, it would be faster to swap the A block to the buffer beforehand, and to take advantage of the fact that the contents of that buffer do not need to retain any order. So rather than rotating the second buffer (which used to be the A block before the block swap) into the previous B block at position ''index'', the values in the B block after ''index'' can simply be block swapped with the last items of the buffer.

The ''floating hole'' in this case refers to the contents of the second internal buffer ''floating'' around the array, and acting as a ''hole'' in the sense that the items do not need to retain their order.

=== Local merges ===
Once the A block has been rotated into the B block, the previous A block is then merged with the B values that follow it, using the second buffer as swap space. When the first A block is dropped behind this refers to the unevenly sized A block at the start, when the second A block is dropped behind it means the first A block, and so forth.

 '''MergeInternal'''(array, A, B, buffer)
     <span style="color:green;">// block swap the values in A with those in 'buffer'</span>
     '''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++
 
     <span style="color:green;">// block swap the remaining part of the buffer with the remaining part of the array</span>
     '''BlockSwap'''(array, buffer.start + A_count, A.start + insert, |A| - A_count)

If the second buffer does not exist, a strictly in-place merge operation must be performed, such as a rotation-based version of the Hwang and Lin algorithm,<ref name="geffert" /><ref>{{cite book|last1=Hwang|first1=F. K.|last2=Lin|first2=S.|title=A Simple Algorithm for Merging Two Disjoint Linearly Ordered Sets|series=[[SIAM Journal on Computing]]|volume=1|year=1972|pages=31–39|doi=10.1137/0201004|issn=0097-5397}}</ref> the Dudzinski and Dydek algorithm,<ref name="dydek">{{cite book|last1=Dudzinski|first1=Krzysztof|last2=Dydek|first2=Andrzej|title=On a Stable Storage Merging Algorithm|series=[[Information Processing Letters]]|volume=12|year=1981|pages=5–8}}</ref> or a repeated binary search and rotate.

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

After dropping the minimum A block and merging the previous A block with the B values that follow it, the new minimum A block must be found within the blocks that are still being rolled through the array. This is handled by running a linear search through those A blocks and comparing the tag values to find the smallest one.

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

These remaining A blocks then continue rolling through the array and being dropped and inserted where they belong. This process repeats until all of the A blocks have been dropped and rotated into the previous B block.

Once the last remaining A block has been dropped behind and inserted into B where it belongs, it should be merged with the remaining B values that follow it. This completes the merge process for that particular pair of A and B subarrays. However, it must then repeat the process for the remaining A and B subarrays for the current level of the merge sort.

Note that the internal buffers can be reused for every set of A and B subarrays for this level of the merge sort, and do not need to be re-extracted or modified in any way.

=== Redistribute ===
After all of the A and B subarrays have been merged, the one or two internal buffers are still left over. The first internal buffer was used for tagging the A blocks, and its contents are still in the same order as before, but the second internal buffer may have had its contents rearranged when it was used as swap space for the merges. This means the contents of the second buffer will need to be sorted using a different algorithm, such as insertion sort. The two buffers must then be redistributed back into the array using the opposite process that was used to create them.

After repeating these steps for every level of the bottom-up merge sort, the block sort is completed.

== Variants ==
Block sort works by extracting two internal buffers, breaking A and B subarrays into evenly sized blocks, rolling and dropping the A blocks into B (using the first buffer to track the order of the A blocks), locally merging using the second buffer as swap space, sorting the second buffer, and redistributing both buffers. While the steps do not change, these subsystems can vary in their actual implementation.

One variant of block sort allows it to use any amount of additional memory provided to it, by using this ''external buffer'' for merging an A subarray or A block with B whenever A fits into it. In this situation it would be identical to a merge sort.

Good choices for the buffer size include:
{| class="wikitable"
|-
! Size
! Notes
|-
! (count + 1)/2
| turns into a full-speed merge sort since all of the A subarrays will fit into it
|-
! {{sqrt|(count + 1)/2}} + 1
| this will be the size of the A blocks at the largest level of merges, so block sort can skip using internal or in-place merges for anything
|-
! 512
| a fixed-size buffer large enough to handle the numerous merges at the smaller levels of the merge sort
|-
! 0
| if the system cannot allocate any extra memory, no memory works well
|}

Rather than tagging the A blocks using the contents of one of the internal buffers, an indirect ''movement-imitation buffer'' can be used instead.<ref name="kim2008" /><ref name="symvonis">{{cite journal |last=Symvonis |first=Antonios |title=Optimal Stable Merging|journal=The Computer Journal |volume=38 |issue=8 |pages=681&ndash;690 |year=1995 |doi=10.1093/comjnl/38.8.681|citeseerx=10.1.1.55.6058 }}</ref> This is an internal buffer defined as ''s1 t s2'', where ''s1'' and ''s2'' are each as large as the number of A and B blocks, and ''t'' contains any values immediately following ''s1'' that are equal to the last value of ''s1'' (thus ensuring that no value in ''s2'' appears in ''s1''). A second internal buffer containing {{sqrt|A}} unique values is still used. The first {{sqrt|A}} values of ''s1'' and ''s2'' are then swapped with each other to encode information into the buffer about which blocks are A blocks and which are B blocks. When an A block at index ''i'' is swapped with a B block at index ''j'' (where the first evenly sized A block is initially at index 0), s1[i] and s1[j] are swapped with s2[i] and s2[j], respectively. This ''imitates the movements'' of the A blocks through B. The unique values in the second buffer are used to determine the original order of the A blocks as they are rolled through the B blocks. Once all of the A blocks have been dropped, the movement-imitation buffer is used to decode whether a given block in the array is an A block or a B block, each A block is rotated into B, and the second internal buffer is used as swap space for the local merges.

The ''second'' value of each A block doesn't necessarily need to be tagged – the first, last, or any other element could be used instead. However, if the first value is tagged, the values will need to be read from the first internal buffer (where they were swapped) when deciding where to drop the minimum A block.

Many sorting algorithms can be used to sort the contents of the second internal buffer, including unstable sorts like [[quicksort]], since the contents of the buffer are guaranteed to be unique. Insertion sort is still recommended, though, for its situational performance and lack of recursion.

=== Implementations ===
Known implementations of Block sort include:
* Kutzner and Kim's implementation in C++.<ref name="implementation"/>
* Wikisort, Mike McFadden's implementation based on Kutzner and Kim's paper.<ref name="wikisort"/>
* GrailSort (and the rewritten HolyGrailSort), Andrey Astrelin's implementation based on Huang and Langston (1992),<ref>{{cite journal |last1=Huang |first1=B-C. |last2=Langston |first2=M. A. |title=Fast Stable Merging and Sorting in Constant Extra Space |journal=The Computer Journal |date=1 December 1992 |volume=35 |issue=6 |pages=643–650 |doi=10.1093/comjnl/35.6.643}}</ref> which ultimately describes a very similar algorithm.<ref>{{multiref|1={{cite web |last1=Astrelin |first1=Andrey |title=Mrrl/GrailSort |website=[[GitHub]] |url=https://github.com/Mrrl/GrailSort |date=6 November 2023}}|2={{cite web |title=HolyGrailSortProject/Rewritten-Grailsort: A diverse array of heavily refactored versions of Andrey Astrelin's GrailSort.h, aiming to be as readable and intuitive as possible |url=https://github.com/HolyGrailSortProject/Rewritten-Grailsort |publisher=The Holy Grail Sort Project |date=14 March 2024}}}}</ref>

== Analysis ==
Block sort is a well-defined and testable class of algorithms, with working implementations available as a merge and as a sort.<ref name="implementation">{{cite web|author=Arne Kutzner|title=In-place Merging Algorithm Benchmarking Tool|url=http://ak.hanyang.ac.kr/research/benchmarking-tool/benchmarking-tool.html|accessdate=2014-03-23|url-status=dead|archiveurl=https://archive.today/20140415030845/http://ak.hanyang.ac.kr/research/benchmarking-tool/benchmarking-tool.html|archivedate=2014-04-15}}</ref><ref name="download">{{cite web|author=Arne Kutzner|title=In-place Merging Algorithm Benchmarking Tool|url=http://itbe.hanyang.ac.kr/research-articles/in-place-merging-algorithm-benchmarking-tool/|accessdate=2016-12-11|archive-url=https://web.archive.org/web/20161220094823/http://itbe.hanyang.ac.kr/research-articles/in-place-merging-algorithm-benchmarking-tool/|archive-date=2016-12-20|url-status=dead}}</ref><ref name="wikisort">{{cite web|title=BonzaiThePenguin/WikiSort: Public domain implementations of block sort for C, C++, and Java|website=[[GitHub]] |url=https://github.com/BonzaiThePenguin/WikiSort|accessdate=2014-03-23}}</ref> This allows its characteristics to be measured and considered.

=== Complexity ===
{{Further|Big O notation#Orders of common functions}}

Block sort begins by performing insertion sort on groups of 16&ndash;31 items in the array. Insertion sort is an {{Math|''O''(''n''<sup>2</sup>)}} operation, so this leads to anywhere from {{Math|''O''(16<sup>2</sup> &times; ''n''/16)}} to {{Math|''O''(31<sup>2</sup> &times; ''n''/31)}}, which is {{Math|''O''(''n'')}} once the [[Big O notation#Example|constant factors are omitted]]. It must also apply an insertion sort on the second internal buffer after each level of merging is completed. However, as this buffer was limited to <math>\sqrt{A}</math> in size, the <math>O(\sqrt{n}^2)</math> operation also ends up being {{Math|''O''(''n'')}}.

Next it must extract two internal buffers for each level of the merge sort. It does so by iterating over the items in the A and B subarrays and incrementing a counter whenever the value changes, and upon finding enough values it rotates them to the start of A or the end of B. In the worst case this will end up searching the entire array before finding <math>\sqrt{A}</math> non-contiguous unique values, which requires {{Math|''O''(''n'')}} comparisons and <math>\sqrt{A}</math> rotations for <math>\sqrt{A}</math> values. This resolves to <math>O(n + \sqrt{n} \times \sqrt{n})</math>, or {{Math|''O''(''n'')}}.

When none of the A or B subarrays contained <math>\sqrt{A}</math> unique values to create the internal buffers, a normally suboptimal in-place merge operation is performed where it repeatedly binary searches and rotates A into B. However, the known lack of unique values within any of the subarrays places a hard limit on the number of binary searches and rotations that will be performed during this step, which is again <math>\sqrt{A}</math> items rotated up to <math>\sqrt{A}</math> times, or {{Math|''O''(''n'')}}. The size of each block is also adjusted to be smaller in the case where it found <math>\sqrt{A}</math> unique values but not 2<math>\sqrt{A}</math>, which further limits the number of unique values contained within any A or B block.

Tagging the A blocks is performed <math>\sqrt{A}</math> times for each A subarray, then the A blocks are rolled through and inserted into the B blocks up to <math>\sqrt{A}</math> times. The local merges retain the same {{Math|''O''(''n'')}} complexity of a standard merge, albeit with more assignments since the values must be swapped rather than copied. The linear search for finding the new minimum A block iterates over <math>\sqrt{A}</math> blocks <math>\sqrt{A}</math> times. And the buffer redistribution process is identical to the buffer extraction but in reverse, and therefore has the same {{Math|''O''(''n'')}} complexity.

After [[Big O notation#Example|omitting all but the highest complexity]] and considering that there are {{Math|log(''n'')}} levels in the outer merge loop, this leads to a final asymptotic complexity of {{Math|''O''(''n'' log(''n''))}} for the worst and average cases. For the best case, where the data is already in order, the merge step performs  {{Math|''n''/16}} comparisons for the first level, then {{Math|''n''/32}}, {{Math|''n''/64}}, {{Math|''n''/128}}, etc. This is a [[1/2 + 1/4 + 1/8 + 1/16 + · · ·|well-known mathematical series]] which resolves to {{Math|''O''(''n'')}}.

=== Memory ===
As block sort is [[Recursion (computer science)|non-recursive]] and does not require the use of [[Memory management#Manual memory management|dynamic allocations]], this leads to constant [[Stack (abstract data type)|stack]] and heap space. It uses {{Math|''O''(1)}} auxiliary memory in a [[transdichotomous model]], which accepts that the {{Math|''O''(log ''n'')}} bits needed to keep track of the ranges for A and B cannot be any greater than 32 or 64 on 32-bit or 64-bit computing systems, respectively, and therefore simplifies to {{Math|''O''(1)}} space for any array that can feasibly be allocated.

=== Stability ===
{{Further|Sorting algorithm#Stability}}
Although items in the array are moved out of order during a block sort, each operation is fully reversible and will have restored the original order of equivalent items by its completion.

Stability requires the first instance of each value in an array before sorting to still be the first instance of that value after sorting. Block sort moves these first instances to the start of the array to create the two internal buffers, but when all of the merges are completed for the current level of the block sort, those values are distributed back to the first sorted position within the array. This maintains stability.

Before rolling the A blocks through the B blocks, each A block has its second value swapped with a value from the first buffer. At that point the A blocks are moved out of order to roll through the B blocks. However, once it finds where it should insert the smallest A block into the previous B block, that smallest A block is moved back to the start of the A blocks and its second value is restored. By the time all of the A blocks have been inserted, the A blocks will be in order again and the first buffer will contain its original values in the original order.

Using the second buffer as swap space when merging an A block with some B values causes the contents of that buffer to be rearranged. However, as the algorithm already ensured the buffer only contains unique values, sorting the contents of the buffer is sufficient to restore their original stable order.

=== Adaptivity ===
Block sort is an [[adaptive sort]] on two levels: first, it skips merging A and B subarrays that are already in order. Next, when A and B need to be merged and are broken into evenly sized blocks, the A blocks are only rolled through B as far as is necessary, and each block is only merged with the B values immediately following it. The more ordered the data originally was, the fewer B values there will be that need to be merged into A.

== Advantages ==
Block sort is a stable sort that does not require additional memory, which is useful in cases where there is not enough free memory to allocate the {{Math|''O''(''n'')}} buffer. When using the ''external buffer'' variant of block sort, it can scale from using {{Math|''O''(''n'')}} memory to progressively smaller buffers as needed, and will still work efficiently within those constraints.

== Disadvantages ==
Block sort does not exploit sorted ranges of data on as fine a level as some other algorithms, such as [[Timsort]].<ref name="tim">{{cite web|author=Tim Peters|title=Re: WikiSort|url=https://lists.archive.carbon60.com/python/dev/1126593?do=post_view_threaded|accessdate=2020-09-13}}</ref> It only checks for these sorted ranges at the two predefined levels: the A and B subarrays, and the A and B blocks. It is also harder to implement and parallelize compared to a merge sort.

== References ==
{{Reflist|30em}}

{{sorting}}

[[Category:Comparison sorts]]
[[Category:Stable sorts]]
[[Category:Articles with example pseudocode]]