Block sort
≈ 8 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
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.
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. 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) power_of_two = FloorPowerOfTwo(array.size) scale = array.size/power_of_two // 1.0 ≤ scale // insertion sort 16–31 items at a time for (merge = 0; merge // 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 // 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[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++ 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 [get the ranges for A and B] [adjust A and B to not include the ranges used by the buffers] // 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 // 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| // move the last B block, which is unevenly sized, // to before the remaining A blocks, by using a rotation Rotate(array, blockB.start - blockA.start, [blockA.start, blockB.end)) lastB = [blockA.start, blockA.start + |blockB|) blockA.start += |blockB| blockA.end += |blockB| minA += |blockB| blockB.end = blockB.start else // roll the leftmost A block to the end by swapping it with the next B block BlockSwap(array, blockA.start, blockB.start, block_size) lastB = [blockA.start, blockA.start + block_size) if (minA = blockA.start) minA = blockA.end blockA.start += block_size blockA.end += block_size blockB.start += block_size // this is equivalent to minimum(blockB.end + block_size, B.end), // but that has the potential to overflow if (blockB.end > B.end - block_size) blockB.end = B.end else blockB.end += block_size // merge the last A block with the remaining B values if (|buffer2| > 0) MergeInternal(array, lastA, [lastA.end, B.end), buffer2) else MergeInPlace(array, lastA, [lastA.end, B.end)) One optimization that can be applied during this step is the floating-hole technique. 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. // block swap the values in A with those in 'buffer' BlockSwap(array, A.start, buffer.start, |A|) A_count = 0, B_count = 0, insert = 0 while (A_count // block swap the remaining part of the buffer with the remaining part of the array BlockSwap(array, buffer.start + A_count, A.start + insert, |A| - A_count) 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, the Dudzinski and Dydek algorithm, or a repeated binary search and rotate. MergeInPlace(array, A, B) while (|A| > 0 and |B| > 0) // find the first place in B where the first item in A needs to be inserted mid = BinaryFirst(array, array[A.start], B) // rotate A into place amount = mid - A.end Rotate(array, amount, [A.start, mid)) // calculate the new A and B ranges B = [mid, B.end) A = [A.start + amount, mid) A.start = BinaryLast(array, array[A.start], A) 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.
Text derived from https://en.wikipedia.org/w/index.php?oldid=1366506567 under CC BY-SA 4.0; modifications have been made.