Block sort

Block sort, or block merge sort, is a sorting algorithm combining at least two merge operations with an insertion sort to arrive at (see Big O notation) in-place stable sorting time. It gets its name from the observation that merging two sorted lists, and , is equivalent to breaking into evenly sized blocks, inserting each block into under special rules, and merging pairs.

One practical algorithm for in-place merging was proposed by Pok-Son Kim and Arne Kutzner in 2008.

Overview The outer loop of block sort is identical to a bottom-up merge sort, where each level of the sort merges pairs of subarrays, and , in sizes of 1, then 2, then 4, 8, 16, and so on, until both subarrays combined are the array itself.

Rather than merging and directly as with traditional methods, a block-based merge algorithm divides into discrete blocks of size (resulting in number of blocks as well), inserts each block into such that the first value of each block is less than or equal (≤) to the value immediately after it, then locally merges each block with any values between it and the next block.

As merges still require a separate buffer large enough to hold the block to be merged, two areas within the array are reserved for this purpose (known as internal buffers). The first two blocks are thus modified to contain the first instance of each value within , with the original contents of those blocks shifted over if necessary. The remaining blocks are then inserted into and merged using one of the two buffers as swap space. This process causes the values in that buffer to be rearranged.

Once every and block of every and 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: bitwise OR >> shift right % modulo ++ and += increment [x, y) range from ≥ x and < y range 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: exchange the positions of two values in an array. Block swap: exchange a range of values within an array with values in a different range of the array. 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 reversals.

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 a value to the next power of two. Thus 63 becomes 32, 64 stays 64, and so forth.

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

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 and subarray are the same size to within one item:

BlockSort(array) power_of_two = FloorPowerOfTwo(array.size) scale = array.size/power_of_two // 1.0 ≤ scale < 2.0

// insertion sort 16–31 items at a time for (merge = 0; merge < power_of_two; merge += 16) start = merge * scale end = start + 16 * scale InsertionSort(array, [start, end))

for (length = 16; length < power_of_two; length += length) for (merge = 0; merge < power_of_two; merge += length * 2) start = merge * scale mid = (merge + length) * scale end = (merge + length * 2) * scale

if (array[end − 1] < array[start]) // the two ranges are in reverse order, so a rotation is enough to merge them Rotate(array, mid − start, [start, end)) else if (array[mid − 1] > array[mid]) Merge(array, A = [start, mid), B = [mid, end)) // else the ranges are already correctly ordered

Fixed-point math may also be used, by representing the scale factor as a fraction integer_part + numerator/denominator:

BlockSort(array) power_of_two = FloorPowerOfTwo(array.size) denominator = power_of_two/16 numerator_step = array.size % denominator integer_step = floor(array.size/denominator)

// insertion sort 16–31 items at a time

while (integer_step < array.size) integer_part = numerator = 0 while (integer_part < array.size) // get the ranges for A and B start = integer_part

integer_part += integer_step numerator += numerator_step if (numerator ≥ denominator) numerator −= denominator integer_part++

mid = integer_part

integer_part += integer_step numerator += numerator_step if (numerator ≥ denominator) numerator −= denominator integer_part++

end = integer_part

if (array[end − 1] < array[start]) Rotate(array, mid − start, [start, end)) else if (array[mid − 1] > array[mid]) Merge(array, A = [start, mid), B = [mid, end))

integer_step += integer_step numerator_step += numerator_step if (numerator_step ≥ denominator) numerator_step −= denominator integer_step++

Extract buffers

The two internal buffers needed for each level of the merge step are created by moving the first 2 first instances of their values within an subarray to the start of . First it iterates over the elements in and counts off the unique values it needs, then it applies array rotations to move those unique values to the start. If A did not contain enough unique values to fill the two buffers (of size each), can be used just as well. In this case it moves the last instance of each value to the end of , with that part of not being included during the merges.

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

If 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 and blocks such that the number of resulting 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 = [number of unique values found] block_size = integer_step/buffer_size + 1

integer_part = numerator = 0 while (integer_part < array.size) [get the ranges for A and B] [adjust A and B to not include the ranges used by the buffers]

Tag A blocks

Once the one or two internal buffers have been created, it begins merging each and 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 block and last 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.

// blockA is the range of the remaining A blocks, // and firstA is the unevenly sized first A block blockA = [A.start, A.end) firstA = [A.start, A.start + |blockA| % block_size)

// swap the second value of each A block with the value in buffer1 for (index = 0, indexA = firstA.end + 1; indexA < blockA.end; indexA += block_size) Swap(array[buffer1.start + index], array[indexA]) index++

lastA = firstA blockB = [B.start, B.start + minimum(block_size, |B|)) blockA.start += |firstA|

Roll and drop

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) // if there's a previous B block and the first value of the minimum A block is ≤ // the last value of the previous B block, then drop that minimum A block behind. // or if there are no B blocks left then keep dropping the remaining A blocks. if ((|lastB| > 0 and array[lastB.end - 1] ≥ array[minA]) or |blockB| = 0) // figure out where to split the previous B block, and rotate it at the split B_split = BinaryFirst(array, array[minA], lastB) B_remaining = lastB.end - B_split

// swap the minimum A block to the beginning of the rolling A blocks BlockSwap(array, blockA.start, minA, block_size)

// restore the second value for the A block Swap(array[blockA.start + 1], array[buffer1.start + indexA]) indexA++

// rotate the A block into the previous B block Rotate(array, blockA.start - B_split, [B_split, blockA.start + block_size))

// locally merge the previous A block with the B values that follow it, // using the second internal buffer as swap space (if it exists) if (|buffer2| > 0) MergeInternal(array, lastA, [lastA.end, B_split), buffer2) else MergeInPlace(array, lastA, [lastA.end, B_split))

// update the range for the remaining A blocks, // and the range remaining from the B block after it was split lastA = [blockA.start - B_remaining, blockA.start - B_remaining + block_size) lastB = [lastA.end, lastA.end + B_remaining)

// if there are no more A blocks remaining, this step is finished blockA.start = blockA.start + block_size if (|blockA| = 0) break

minA = [new minimum A block] (see below) else if (|blockB| < block_size) // move the last B block, which is unevenly sized, // to before the remaining A blocks, by using a rotation Rotate(array, blockB.start - blockA.start, [blockA.start, blockB.end))

blockA.start += block_size blockA.end += block_size blockB.start += block_size

// this is equivalent to minimum(blockB.end + block_size, B.end), // but that has the potential to overflow if (blockB.end > B.end - block_size) blockB.end = B.end else blockB.end += block_size

// merge the last A block with the remaining B values if (|buffer2| > 0) MergeInternal(array, lastA, [lastA.end, B.end), buffer2) else MergeInPlace(array, lastA, [lastA.end, B.end))

Block sort

Bron en licentie