Block sort - Knowledge

768: 873: 1141:. 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 946: 2513:

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,

1961:

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

1754:

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

1446:

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.

1261:

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

1172:

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

414:

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

2530:

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.

1438:

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

1292:

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

1280:

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

2517:

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

966:

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

2509:

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

1304:

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

1293:

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.

957:

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.

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.

735:(numerator ≥ denominator) numerator −= denominator integer_part++ mid = integer_part integer_part += integer_step numerator += numerator_step 543:: 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 1219:

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.

2492:) 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 O(1) space for any array that can feasibly be allocated. 961:

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

1276:

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.

34: 670:(merge = 0; merge < power_of_two; merge += length * 2) start = merge * scale mid = (merge + length) * scale end = (merge + length * 2) * scale 908:

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

1903: 794:

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

2555:. 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. 1481:

Block sort is a well-defined and testable class of algorithms, with working implementations available as a merge and as a sort. This allows its characteristics to be measured and considered.

2506:

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.

2167:

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

1629: 1579: 1095:(minA = blockA.start) minA = blockA.end blockA.start += block_size blockA.end += block_size blockB.start += block_size 2960:"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" 2539:

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 O(n) buffer. When using the

1720: 573:: 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 1284:

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.

900:

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

2317: 2213: 2189: 2136: 2112: 2085: 2061: 2008: 1984: 1959: 1854: 1830: 1777: 1686: 2977: 2277: 1529: 1472:

GrailSort (and the rewritten HolyGrailSort), Andrey Astrelin's implementation based on Huang and Langston (1992), which ultimately describes a very similar algorithm.

2429: 1454:, 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. 2462: 2401: 2373: 2345: 2242: 2165: 2037: 1932: 1806: 1749: 1658: 949:

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.

2543:

variant of block sort, it can scale from using O(n) memory to progressively smaller buffers as needed, and will still work efficiently within those constraints.

857:

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.

739:(numerator ≥ denominator) numerator −= denominator integer_part++ end = integer_part 1426:

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

1664:. 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 630:

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

2866: 1052:

lastA = [blockA.start - B_remaining, blockA.start - B_remaining + block_size) lastB = [lastA.end, lastA.end + B_remaining)

614:(x) x = x | (x >> 1) x = x | (x >> 2) x = x | (x >> 4) x = x | (x >> 8) x = x | (x >> 16) 1346:

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

2640: 755:(array, A = [start, mid), B = [mid, end)) integer_step += integer_step numerator_step += numerator_step 2432: 2510:

level of the block sort, those values are distributed back to the first sorted position within the array. This maintains stability.

33: 658:(merge = 0; merge < power_of_two; merge += 16) start = merge * scale end = start + 16 * scale 480: 2734: 1439:

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.

2215:

times. And the buffer redistribution process is identical to the buffer extraction but in reverse, and therefore has the same

1312:

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.

712:(array.size) denominator = power_of_two/16 numerator_step = array.size % denominator integer_step = 2694: 2981: 731:

start = integer_part integer_part += integer_step numerator += numerator_step

1434:(where the first evenly sized A block is initially at index 0), s1 and s1 are swapped with s2 and s2, respectively. This 1859: 1091:(array, blockA.start, blockB.start, block_size) lastB = [blockA.start, blockA.start + block_size) 395:

and merged using one of the two buffers as swap space. This process causes the values in that buffer to be rearranged.

1450:

Many sorting algorithms can be used to sort the contents of the second internal buffer, including unstable sorts like

1305:

redistributing both buffers. While the steps do not change, these subsystems can vary in their actual implementation.

3040: 2584: 462: 567:: for each item in the array, loop backward and find where it needs to be inserted, then insert it at that position. 3063: 2319:

for the worst and average cases. For the best case, where the data is already in order, the merge step performs

1495:

Block sort begins by performing insertion sort on groups of 16–31 items in the array. Insertion sort is an

3371: 2811: 2607: 3003: 2477: 2732:

Geffert, Viliam; Katajainen, Jykri; Pasanen, Tomi (April 2000). "Asymptotically efficient in-place merging".

2870: 2920:

Huang, B-C.; Langston, M. A. (1 December 1992). "Fast Stable Merging and Sorting in Constant Extra Space".

2473: 162: 136: 114: 88: 2531:

The more ordered the data originally was, the fewer B values there will be that need to be merged into A.

1584: 1534: 1490: 759:(numerator_step ≥ denominator) numerator_step −= denominator integer_step++ 3404: 1308:

One variant of block sort allows it to use any amount of additional memory provided to it, by using this

604: 2551:

Block sort does not exploit sorted ranges of data on as fine a level as some other algorithms, such as

2481: 1354:

a fixed-size buffer large enough to handle the numerous merges at the smaller levels of the merge sort

296:, in sizes of 1, then 2, then 4, 8, 16, and so on, until both subarrays combined are the array itself. 3202: 1691: 1296:

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

3504: 3078: 2776: 2715: 2114:

times for each A subarray, then the A blocks are rolled through and inserted into the B blocks up to

20: 2605:

Mannila, Heikki; Ukkonen, Esko (14 May 1984). "A Simple Linear Time Algorithm for In-Situ Merging".

3376: 2839: 2748: 559:: find a particular value in an array by checking every single element in order, until it is found. 442: 2282: 841:

does not contain enough unique values either, it pulls out the largest number of unique values it

775:

The two internal buffers needed for each level of the merge step are created by moving the first 2

2687: 2194: 2170: 2117: 2093: 2066: 2042: 1989: 1965: 1940: 1835: 1811: 1758: 1667: 539: 523: 1368:

Rather than tagging the A blocks using the contents of one of the internal buffers, an indirect

574: 415:

level of the outer bottom-up merge sort, at which point the array will have been stably sorted.

281: 3284: 3164: 3118: 3088: 2834: 2743: 2501: 2485: 695: 223: 2959: 2254: 1498: 518:

Additionally, block sort relies on the following operations as part of its overall algorithm:

3509: 3445: 3033: 2895:"BonzaiThePenguin/WikiSort: Public domain implementations of block sort for C, C++, and Java" 531: 3424: 3289: 3144: 2406: 535:: exchange a range of values within an array with values in a different range of the array. 81: 2438: 2378: 2350: 2322: 2218: 2141: 2013: 1908: 1782: 1725: 1634: 8: 3440: 3179: 2677: 432: 3330: 3305: 3279: 3083: 2660: 2248: 1661: 929:(index = 0, indexA = firstA.end + 1; indexA < blockA.end; indexA += block_size) 375:

block to be merged, two areas within the array are reserved for this purpose (known as

2757: 2087:, which further limits the number of unique values contained within any A or B block. 860:

buffer_size = block_size = integer_step/buffer_size + 1 integer_part = numerator = 0

387:, with the original contents of those blocks shifted over if necessary. The remaining 3149: 3049: 2788: 2690: 2620: 189: 71: 3217: 3391: 3258: 3026: 2929: 2844: 2780: 2753: 2616: 2575: 2039:. The size of each block is also adjusted to be smaller in the case where it found 1211:// block swap the remaining part of the buffer with the remaining part of the array 1105: 922:

blockA = [A.start, A.end) firstA = [A.start, A.start + |blockA| % block_size)

767: 619: 452: 226:

sorting time. It gets its name from the observation that merging two sorted lists,

165: 1112:(blockB.end > B.end - block_size) blockB.end = B.end 723:(integer_step < array.size) integer_part = numerator = 0 3452: 3335: 3207: 3108: 3103: 3093: 1332:

turns into a full-speed merge sort since all of the A subarrays will fit into it

1186:(array, A.start, buffer.start, |A|) A_count = 0, B_count = 0, insert = 0 1024:(array, blockA.start - B_split, [B_split, blockA.start + block_size)) 979:// the last value of the previous B block, then drop that minimum A block behind. 193: 139: 117: 91: 1269:(findA = minA + block_size; findA < blockA.end - 1; findA += block_size) 976:// if there's a previous B block and the first value of the minimum A block is ≤ 607:

a value to the next power of two. Thus 63 becomes 32, 64 stays 64, and so forth.

3457: 3366: 3233: 3187: 3113: 3068: 2894: 2683: 2279:

levels in the outer merge loop, this leads to a final asymptotic complexity of

892:

Once the one or two internal buffers have been created, it begins merging each

563: 216: 197: 2933: 2848: 1003:(array, array, lastB) B_remaining = lastB.end - B_split 982:// or if there are no B blocks left then keep dropping the remaining A blocks. 872: 3498: 3325: 3098: 2792: 2527: 997:// figure out where to split the previous B block, and rotate it at the split 676:// the two ranges are in reverse order, so a rotation is enough to merge them 555: 1086:// roll the leftmost A block to the end by swapping it with the next B block 383:

blocks are thus modified to contain the first instance of each value within

307:

directly as with traditional methods, a block-based merge algorithm divides

3340: 3253: 3123: 1236:// find the first place in B where the first item in A needs to be inserted 945: 62:, locally merge them, sort the second buffer, and redistribute the buffers. 1469:

Wikisort, Mike McFadden's implementation based on Kutzner and Kim's paper.

3473: 3315: 3139: 3073: 953:

After defining and tagging the A blocks in this manner, the A blocks are

880:

blocks using values from the first internal buffer. Note that the first

547:

position to insert a value in the sorted array, and one which finds the

3419: 3381: 3345: 3274: 3212: 3197: 3159: 1254:

B = [mid, B.end) A = [A.start + amount, mid) A.start =

1026:// locally merge the previous A block with the B values that follow it, 933:(array, array) index++ lastA = firstA blockB = [B.start, B.start + 272:

in-place merging was proposed by Pok-Son Kim and Arne Kutzner in 2008.

2638:[An Optimal Ordering Algorithm without a Field of Operation]. 622:

system) x = x | (x >> 32) return x - (x >> 1)

3414: 3350: 3320: 3310: 3248: 3243: 3238: 3169: 3154: 3018: 2635: 1451: 1362:

if the system cannot allocate any extra memory, no memory works well

666:(length = 16; length < power_of_two; length += length) 16:

Efficient sorting algorithm that combines insert and merge operations

2951: 2784: 1005:// swap the minimum A block to the beginning of the rolling A blocks 3483: 3478: 3192: 371:

As merges still require a separate buffer large enough to hold the

220: 40:

Insertion sort groups of 16, extract two internal buffers, tag the

1156:

in this case refers to the contents of the second internal buffer

924:// swap the second value of each A block with the value in buffer1 3409: 2773:

A Simple Algorithm for Merging Two Disjoint Linearly Ordered Sets

2552: 1216:(array, buffer.start + A_count, A.start + insert, |A| - A_count) 1054:// if there are no more A blocks remaining, this step is finished 698:

may also be used, by representing the scale factor as a fraction

1029:// using the second internal buffer as swap space (if it exists) 2899: 1164:

in the sense that the items do not need to retain their order.

1149:

can simply be block swapped with the last items of the buffer.

2587:. Vol. 4978. Springer Berlin Heidelberg. pp. 246–257 1050:// and the range remaining from the B block after it was split 2712:

Stable Sorting and Merging with Optimal Space and Time Bounds

1137:

One optimization that can be applied during this step is the

1372:

can be used instead. This is an internal buffer defined as

1209:(array, array) B_count++ insert++ 1281:

and B subarrays for the current level of the merge sort.

1038:(array, lastA, [lastA.end, B_split), buffer2) 689:(array, A = [start, mid), B = [mid, end)) 2731: 1962:

that will be performed during this step, which is again

1076:// to before the remaining A blocks, by using a rotation 1384:

are each as large as the number of A and B blocks, and

423:

The following operators are used in the code examples:

1755:

will end up searching the entire array before finding

2825:

Symvonis, Antonios (1995). "Optimal Stable Merging".

2636:"Оптимальный алгоритм упорядочения без рабочего поля" 2441: 2409: 2381: 2353: 2325: 2285: 2257: 2221: 2197: 2173: 2144: 2120: 2096: 2069: 2045: 2016: 1992: 1968: 1943: 1911: 1862: 1838: 1814: 1785: 1761: 1728: 1694: 1670: 1637: 1587: 1537: 1501: 1118:// merge the last A block with the remaining B values 1181:// block swap the values in A with those in 'buffer' 1056:blockA.start = blockA.start + block_size 805:

can be used just as well. In this case it moves the

648:(array.size) scale = array.size/power_of_two 2484:and heap space. It uses O(1) auxiliary memory in a 1010:(array, blockA.start, minA, block_size) 527:: exchange the positions of two values in an array. 2456: 2423: 2395: 2367: 2339: 2311: 2271: 2236: 2207: 2183: 2159: 2130: 2106: 2079: 2055: 2031: 2002: 1978: 1953: 1926: 1898:{\displaystyle O(n+{\sqrt {n}}\times {\sqrt {n}})} 1897: 1848: 1824: 1800: 1771: 1743: 1714: 1680: 1652: 1623: 1573: 1523: 1073:// move the last B block, which is unevenly sized, 747:(array, mid − start, [start, end)) 681:(array, mid − start, [start, end)) 2860: 2858: 920:// and firstA is the unevenly sized first A block 917:// blockA is the range of the remaining A blocks, 592:(array, [range.start, range.start + amount)) 3496: 1491:Big O notation § Orders of common functions 1045:(array, lastA, [lastA.end, B_split)) 827:(integer_step < array.size) block_size = 691:// else the ranges are already correctly ordered 1127:(array, lastA, [lastA.end, B.end), buffer2) 1047:// update the range for the remaining A blocks, 1019:// rotate the A block into the previous B block 638:subarray are the same size to within one item: 280:The outer loop of block sort is identical to a 2978:"In-place Merging Algorithm Benchmarking Tool" 2867:"In-place Merging Algorithm Benchmarking Tool" 2855: 2805: 2604: 1017:(array, array) indexA++ 727:(integer_part < array.size) 3034: 2962:. The Holy Grail Sort Project. 14 March 2024. 2919: 2806:Dudzinski, Krzysztof; Dydek, Andrzej (1981). 1779:non-contiguous unique values, which requires 1462:Known implementations of Block sort include: 1202:(array, array) A_count++ 771:The buffer extraction process for block sort. 718:// insertion sort 16–31 items at a time 1937:When none of the A or B subarrays contained 937:(block_size, |B|)) blockA.start += |firstA| 2889: 2887: 2641:Proceedings of the USSR Academy of Sciences 1012:// restore the second value for the A block 596:(array, [range.start + amount, range.end)) 3041: 3027: 2675: 2669: 2573: 1531:operation, so this leads to anywhere from 1388:contains any values immediately following 1315:Good choices for the buffer size include: 1173:it means the first A block, and so forth. 834:buffer_size = integer_step/block_size + 1 782:first instances of their values within an 38:Block sort stably sorting numbers 1 to 16. 2838: 2747: 2727: 2725: 2569: 2567: 853:blocks such that the number of resulting 790:. First it iterates over the elements in 2975: 2969: 2949: 2884: 2864: 2824: 2818: 2770: 2138:times. The local merges retain the same 1466:Kutzner and Kim's implementation in C++. 1273:(array < array) minA = findA 1250:(array, amount, [A.start, mid)) 944: 871: 766: 2658: 2634:Kronrod, M. Alexander (February 1969). 2633: 2598: 2249:omitting all but the highest complexity 1411:unique values is still used. The first 1404:). A second internal buffer containing 653:// insertion sort 16–31 items at a time 348:block is less than or equal (≤) to the 288:of the sort merges pairs of subarrays, 3497: 3048: 3001: 2722: 2627: 2564: 2347:comparisons for the first level, then 1071:(|blockB| < block_size) 821:not being included during the merges. 751:(array > array) 743:(array < array) 685:(array > array) 674:(array < array) 3022: 2808:On a Stable Storage Merging Algorithm 2709: 970:minA = blockA.start indexA = 0 2950:Astrelin, Andrey (6 November 2023). 2799: 2703: 2574:Kutzner, Arne; Kim, Pok-Son (2008). 1624:{\displaystyle O(31^{2}\times n/31)} 1574:{\displaystyle O(16^{2}\times n/16)} 1392:that are equal to the last value of 700:integer_part + numerator/denominator 2995: 2577:Ratio Based Stable In-Place Merging 1430:is swapped with a B block at index 1252:// calculate the new A and B ranges 1134:(array, lastA, [lastA.end, B.end)) 845:find, then adjusts the size of the 13: 2502:Sorting algorithm § Stability 2090:Tagging the A blocks is performed 1457: 1160:around the array, and acting as a 1145:, the values in the B block after 1034:(|buffer2| > 0) 762: 344:such that the first value of each 14: 3521: 2585:Lecture Notes in Computer Science 1104:// but that has the potential to 1101:(blockB.end + block_size, B.end), 352:value immediately after it, then 336:of blocks as well), inserts each 250:under special rules, and merging 2718:. Vol. 6. pp. 351–372. 2546: 2476:and does not require the use of 1715:{\displaystyle O{\sqrt {n}}^{2}} 1396:(thus ensuring that no value in 940: 716:(array.size/denominator) 32: 3064:Computational complexity theory 2940: 2913: 2779:. Vol. 1. pp. 31–39. 2488:, which accepts that the O(log 2251:and considering that there are 1287: 1167: 867: 864:(integer_part < array.size) 364:values between it and the next 2812:Information Processing Letters 2771:Hwang, F. K.; Lin, S. (1972). 2764: 2676:Warren Jr., Henry S. (2013) . 2652: 2608:Information Processing Letters 2451: 2445: 2433:well-known mathematical series 2306: 2289: 2231: 2225: 2154: 2148: 2026: 2020: 1921: 1915: 1892: 1866: 1795: 1789: 1738: 1732: 1647: 1641: 1618: 1591: 1568: 1541: 1518: 1505: 1060:(|blockA| = 0) 809:instance of each value to the 708:(array) power_of_two = 644:(array) power_of_two = 391:blocks are then inserted into 1: 2814:. Vol. 12. pp. 5–8. 2758:10.1016/S0304-3975(98)00162-5 2558: 2534: 2521: 1722:operation also ends up being 1484: 1246:amount = mid - A.end 729:// get the ranges for A and B 662:(array, [start, end)) 625: 311:into discrete blocks of size 2735:Theoretical Computer Science 2621:10.1016/0020-0190(84)90112-1 2495: 2312:{\displaystyle O(n\log {n})} 1662:constant factors are omitted 1198:(array ≤ array) 1116:blockB.end += block_size 418: 257:One practical algorithm for 234:, is equivalent to breaking 7: 2208:{\displaystyle {\sqrt {A}}} 2184:{\displaystyle {\sqrt {A}}} 2131:{\displaystyle {\sqrt {A}}} 2107:{\displaystyle {\sqrt {A}}} 2080:{\displaystyle {\sqrt {A}}} 2056:{\displaystyle {\sqrt {A}}} 2003:{\displaystyle {\sqrt {A}}} 1979:{\displaystyle {\sqrt {A}}} 1954:{\displaystyle {\sqrt {A}}} 1849:{\displaystyle {\sqrt {A}}} 1825:{\displaystyle {\sqrt {A}}} 1772:{\displaystyle {\sqrt {A}}} 1681:{\displaystyle {\sqrt {A}}} 1476: 1299: 584:(array, amount, range) 275: 10: 3526: 3372:Batcher odd–even mergesort 2710:Pardo, Luis Trabb (1977). 2499: 1488: 1262:to find the smallest one. 1242:(array, array, B) 1194:B_count < |B|) 1179:(array, A, B, buffer) 1123:(|buffer2| > 0) 18: 3466: 3433: 3390: 3359: 3298: 3267: 3226: 3178: 3132: 3056: 2777:SIAM Journal on Computing 2716:SIAM Journal on Computing 2480:, this leads to constant 2467: 1856:values. This resolves to 1370:movement-imitation buffer 1097:// this is equivalent to 995:|blockB| = 0) 888:block are unevenly sized. 786:subarray to the start of 161: 135: 113: 87: 77: 67: 31: 21:Block-sorting compression 3377:Pairwise sorting network 2272:{\displaystyle \log {n}} 1524:{\displaystyle O(n^{2})} 498:range.end – range.start 19:Not to be confused with 3405:Kirkpatrick–Reisch sort 2934:10.1093/comjnl/35.6.643 2849:10.1093/comjnl/38.8.681 2688:Pearson Education, Inc. 2063:unique values but not 2 1139:floating-hole technique 650:// 1.0 ≤ scale < 2.0 192:combining at least two 3285:Oscillating merge sort 3165:Proportion extend sort 3119:Transdichotomous model 2486:transdichotomous model 2458: 2425: 2397: 2369: 2341: 2313: 2273: 2238: 2209: 2185: 2161: 2132: 2108: 2081: 2057: 2033: 2004: 1980: 1955: 1928: 1899: 1850: 1826: 1802: 1773: 1745: 1716: 1682: 1654: 1625: 1575: 1525: 1436:imitates the movements 1244:// rotate A into place 967:into B at that index. 950: 889: 772: 3446:Pre-topological order 2659:Bentley, Jon (2006). 2500:Further information: 2459: 2426: 2424:{\displaystyle n/128} 2398: 2370: 2342: 2314: 2274: 2239: 2210: 2186: 2162: 2133: 2109: 2082: 2058: 2034: 2005: 1981: 1956: 1929: 1900: 1851: 1827: 1803: 1774: 1746: 1717: 1683: 1655: 1626: 1576: 1526: 1489:Further information: 948: 875: 770: 3425:Merge-insertion sort 3290:Polyphase merge sort 3145:Cocktail shaker sort 2922:The Computer Journal 2827:The Computer Journal 2457:{\displaystyle O(n)} 2439: 2407: 2396:{\displaystyle n/64} 2379: 2368:{\displaystyle n/32} 2351: 2340:{\displaystyle n/16} 2323: 2283: 2255: 2237:{\displaystyle O(n)} 2219: 2195: 2171: 2160:{\displaystyle O(n)} 2142: 2118: 2094: 2067: 2043: 2032:{\displaystyle O(n)} 2014: 1990: 1986:items rotated up to 1966: 1941: 1927:{\displaystyle O(n)} 1909: 1860: 1836: 1812: 1801:{\displaystyle O(n)} 1783: 1759: 1744:{\displaystyle O(n)} 1726: 1692: 1668: 1653:{\displaystyle O(n)} 1635: 1585: 1535: 1499: 1265:minA = blockA.start 1234:|B| > 0) 817:, with that part of 299:Rather than merging 282:bottom-up merge sort 3441:Topological sorting 3203:Cartesian tree sort 2478:dynamic allocations 588:(array, range) 196:operations with an 28: 3331:Interpolation sort 3306:American flag sort 3299:Distribution sorts 3280:Cascade merge sort 3050:Sorting algorithms 2662:Programming Pearls 2454: 2435:which resolves to 2421: 2393: 2365: 2337: 2309: 2269: 2234: 2205: 2181: 2157: 2128: 2104: 2077: 2053: 2029: 2000: 1976: 1951: 1924: 1895: 1846: 1822: 1798: 1769: 1741: 1712: 1678: 1650: 1621: 1571: 1521: 1258:(array, array, A) 1226:(array, A, B) 1190:(A_count < |A| 951: 890: 773: 601:Floor power of two 495:|range| 238:into evenly sized 26: 3492: 3491: 3467:Impractical sorts 2696:978-0-321-84268-8 2526:Block sort is an 2472:As block sort is 2431:, etc. This is a 2203: 2179: 2126: 2102: 2075: 2051: 1998: 1974: 1949: 1890: 1880: 1844: 1820: 1767: 1704: 1676: 1366: 1365: 987:((|lastB| > 0 516: 515: 379:). The first two 242:, inserting each 190:sorting algorithm 179: 178: 72:Sorting algorithm 3517: 3505:Comparison sorts 3400:Block merge sort 3360:Concurrent sorts 3259:Patience sorting 3043: 3036: 3029: 3020: 3019: 3014: 3013: 3011: 3010: 2999: 2993: 2992: 2990: 2989: 2980:. Archived from 2973: 2967: 2963: 2955: 2952:"Mrrl/GrailSort" 2944: 2938: 2937: 2917: 2911: 2910: 2908: 2907: 2891: 2882: 2881: 2879: 2878: 2869:. Archived from 2862: 2853: 2852: 2842: 2822: 2816: 2815: 2803: 2797: 2796: 2768: 2762: 2761: 2751: 2742:(1–2): 159–181. 2729: 2720: 2719: 2707: 2701: 2700: 2699:. 0-321-84268-5. 2679:Hacker's Delight 2673: 2667: 2666: 2656: 2650: 2649: 2631: 2625: 2624: 2602: 2596: 2595: 2593: 2592: 2582: 2571: 2463: 2461: 2460: 2455: 2430: 2428: 2427: 2422: 2417: 2402: 2400: 2399: 2394: 2389: 2374: 2372: 2371: 2366: 2361: 2346: 2344: 2343: 2338: 2333: 2318: 2316: 2315: 2310: 2305: 2278: 2276: 2275: 2270: 2268: 2243: 2241: 2240: 2235: 2214: 2212: 2211: 2206: 2204: 2199: 2190: 2188: 2187: 2182: 2180: 2175: 2166: 2164: 2163: 2158: 2137: 2135: 2134: 2129: 2127: 2122: 2113: 2111: 2110: 2105: 2103: 2098: 2086: 2084: 2083: 2078: 2076: 2071: 2062: 2060: 2059: 2054: 2052: 2047: 2038: 2036: 2035: 2030: 2009: 2007: 2006: 2001: 1999: 1994: 1985: 1983: 1982: 1977: 1975: 1970: 1960: 1958: 1957: 1952: 1950: 1945: 1933: 1931: 1930: 1925: 1904: 1902: 1901: 1896: 1891: 1886: 1881: 1876: 1855: 1853: 1852: 1847: 1845: 1840: 1831: 1829: 1828: 1823: 1821: 1816: 1808:comparisons and 1807: 1805: 1804: 1799: 1778: 1776: 1775: 1770: 1768: 1763: 1750: 1748: 1747: 1742: 1721: 1719: 1718: 1713: 1711: 1710: 1705: 1700: 1687: 1685: 1684: 1679: 1677: 1672: 1659: 1657: 1656: 1651: 1630: 1628: 1627: 1622: 1614: 1603: 1602: 1580: 1578: 1577: 1572: 1564: 1553: 1552: 1530: 1528: 1527: 1522: 1517: 1516: 1417: 1416: 1410: 1409: 1342: 1341: 1318: 1317: 1253: 1245: 1237: 1212: 1182: 1119: 1108: 1102: 1087: 1077: 1074: 1055: 1051: 1048: 1030: 1027: 1020: 1013: 1006: 998: 983: 980: 977: 925: 921: 918: 833: 832: 800: 799: 781: 780: 730: 719: 701: 696:Fixed-point math 692: 677: 654: 651: 426: 425: 413: 409: 405: 401: 394: 390: 386: 382: 377:internal buffers 374: 367: 363: 359: 351: 347: 343: 339: 332: 331: 330: 321: 320: 319: 310: 306: 302: 295: 291: 271: 253: 249: 245: 237: 233: 229: 214: 186:block merge sort 175: 166:space complexity 157: 131: 109: 61: 57: 54:each), roll the 53: 51: 50: 44:blocks (of size 43: 36: 29: 25: 3525: 3524: 3520: 3519: 3518: 3516: 3515: 3514: 3495: 3494: 3493: 3488: 3462: 3453:Pancake sorting 3429: 3386: 3355: 3336:Pigeonhole sort 3294: 3263: 3227:Insertion sorts 3222: 3208:Tournament sort 3180:Selection sorts 3174: 3128: 3109:Integer sorting 3104:Sorting network 3094:Comparison sort 3052: 3047: 3017: 3008: 3006: 3000: 2996: 2987: 2985: 2974: 2970: 2966: 2958: 2945: 2941: 2918: 2914: 2905: 2903: 2893: 2892: 2885: 2876: 2874: 2863: 2856: 2823: 2819: 2804: 2800: 2785:10.1137/0201004 2769: 2765: 2730: 2723: 2708: 2704: 2697: 2674: 2670: 2665:(2nd ed.). 2657: 2653: 2648:(6): 1256–1258. 2632: 2628: 2603: 2599: 2590: 2588: 2580: 2572: 2565: 2561: 2549: 2541:external buffer 2537: 2524: 2504: 2498: 2470: 2440: 2437: 2436: 2413: 2408: 2405: 2404: 2385: 2380: 2377: 2376: 2357: 2352: 2349: 2348: 2329: 2324: 2321: 2320: 2301: 2284: 2281: 2280: 2264: 2256: 2253: 2252: 2220: 2217: 2216: 2198: 2196: 2193: 2192: 2174: 2172: 2169: 2168: 2143: 2140: 2139: 2121: 2119: 2116: 2115: 2097: 2095: 2092: 2091: 2070: 2068: 2065: 2064: 2046: 2044: 2041: 2040: 2015: 2012: 2011: 1993: 1991: 1988: 1987: 1969: 1967: 1964: 1963: 1944: 1942: 1939: 1938: 1910: 1907: 1906: 1885: 1875: 1861: 1858: 1857: 1839: 1837: 1834: 1833: 1815: 1813: 1810: 1809: 1784: 1781: 1780: 1762: 1760: 1757: 1756: 1727: 1724: 1723: 1706: 1699: 1698: 1693: 1690: 1689: 1671: 1669: 1666: 1665: 1636: 1633: 1632: 1610: 1598: 1594: 1586: 1583: 1582: 1560: 1548: 1544: 1536: 1533: 1532: 1512: 1508: 1500: 1497: 1496: 1493: 1487: 1479: 1460: 1458:Implementations 1414: 1412: 1407: 1405: 1339: 1337: 1310:external buffer 1302: 1290: 1274: 1259: 1251: 1243: 1235: 1217: 1210: 1180: 1170: 1135: 1117: 1103: 1096: 1085: 1075: 1072: 1053: 1049: 1046: 1028: 1025: 1018: 1011: 1004: 996: 991:array ≥ array) 981: 978: 975: 943: 938: 923: 919: 916: 907: 904:block and last 903: 899: 895: 887: 884:block and last 883: 879: 870: 865: 856: 852: 848: 840: 835: 830: 828: 820: 816: 804: 797: 795: 793: 789: 785: 778: 776: 765: 763:Extract buffers 760: 728: 717: 710:FloorPowerOfTwo 699: 693: 690: 675: 652: 649: 646:FloorPowerOfTwo 637: 633: 628: 623: 612:FloorPowerOfTwo 597: 421: 411: 407: 406:block of every 403: 399: 392: 388: 384: 380: 372: 365: 361: 360:block with any 357: 349: 345: 341: 337: 326: 324: 323: 315: 313: 312: 308: 304: 300: 293: 289: 278: 258: 251: 247: 243: 235: 231: 227: 201: 170: 144: 122: 96: 63: 59: 58:blocks through 55: 48: 46: 45: 41: 39: 24: 17: 12: 11: 5: 3523: 3513: 3512: 3507: 3490: 3489: 3487: 3486: 3481: 3476: 3470: 3468: 3464: 3463: 3461: 3460: 3458:Spaghetti sort 3455: 3450: 3449: 3448: 3437: 3435: 3431: 3430: 3428: 3427: 3422: 3417: 3412: 3407: 3402: 3396: 3394: 3388: 3387: 3385: 3384: 3379: 3374: 3369: 3367:Bitonic sorter 3363: 3361: 3357: 3356: 3354: 3353: 3348: 3343: 3338: 3333: 3328: 3323: 3318: 3313: 3308: 3302: 3300: 3296: 3295: 3293: 3292: 3287: 3282: 3277: 3271: 3269: 3265: 3264: 3262: 3261: 3256: 3251: 3246: 3241: 3236: 3234:Insertion sort 3230: 3228: 3224: 3223: 3221: 3220: 3218:Weak-heap sort 3215: 3210: 3205: 3200: 3195: 3190: 3188:Selection sort 3184: 3182: 3176: 3175: 3173: 3172: 3167: 3162: 3157: 3152: 3147: 3142: 3136: 3134: 3133:Exchange sorts 3130: 3129: 3127: 3126: 3121: 3116: 3111: 3106: 3101: 3096: 3091: 3086: 3081: 3076: 3071: 3069:Big O notation 3066: 3060: 3058: 3054: 3053: 3046: 3045: 3038: 3031: 3023: 3016: 3015: 3004:"Re: WikiSort" 2994: 2976:Arne Kutzner. 2968: 2965: 2964: 2956: 2946: 2939: 2928:(6): 643–650. 2912: 2883: 2865:Arne Kutzner. 2854: 2840:10.1.1.55.6058 2833:(8): 681–690. 2817: 2798: 2763: 2749:10.1.1.22.5750 2721: 2702: 2695: 2684:Addison Wesley 2682:(2 ed.). 2668: 2651: 2644:(in Russian). 2626: 2615:(4): 203–208. 2597: 2562: 2560: 2557: 2548: 2545: 2536: 2533: 2523: 2520: 2497: 2494: 2469: 2466: 2453: 2450: 2447: 2444: 2420: 2416: 2412: 2392: 2388: 2384: 2364: 2360: 2356: 2336: 2332: 2328: 2308: 2304: 2300: 2297: 2294: 2291: 2288: 2267: 2263: 2260: 2233: 2230: 2227: 2224: 2202: 2178: 2156: 2153: 2150: 2147: 2125: 2101: 2074: 2050: 2028: 2025: 2022: 2019: 1997: 1973: 1948: 1923: 1920: 1917: 1914: 1894: 1889: 1884: 1879: 1874: 1871: 1868: 1865: 1843: 1832:rotations for 1819: 1797: 1794: 1791: 1788: 1766: 1740: 1737: 1734: 1731: 1709: 1703: 1697: 1675: 1649: 1646: 1643: 1640: 1620: 1617: 1613: 1609: 1606: 1601: 1597: 1593: 1590: 1570: 1567: 1563: 1559: 1556: 1551: 1547: 1543: 1540: 1520: 1515: 1511: 1507: 1504: 1486: 1483: 1478: 1475: 1474: 1473: 1470: 1467: 1459: 1456: 1364: 1363: 1360: 1356: 1355: 1352: 1348: 1347: 1344: 1334: 1333: 1330: 1329:(count + 1)/2 1326: 1325: 1322: 1301: 1298: 1289: 1286: 1264: 1222: 1175: 1169: 1166: 974:(true) 969: 942: 939: 915: 905: 901: 897: 893: 885: 881: 877: 869: 866: 859: 854: 850: 846: 838: 823: 818: 814: 802: 791: 787: 783: 764: 761: 704: 640: 635: 631: 627: 624: 610: 609: 608: 580: 579: 578: 571:Array rotation 568: 564:Insertion sort 560: 552: 536: 528: 514: 513: 504: 500: 499: 496: 492: 491: 478: 466: 465: 460: 456: 455: 450: 446: 445: 440: 436: 435: 430: 420: 417: 354:locally merges 322:(resulting in 277: 274: 217:Big O notation 198:insertion sort 177: 176: 168: 159: 158: 142: 133: 132: 120: 111: 110: 94: 85: 84: 79: 78:Data structure 75: 74: 69: 65: 64: 37: 15: 9: 6: 4: 3: 2: 3522: 3511: 3508: 3506: 3503: 3502: 3500: 3485: 3482: 3480: 3477: 3475: 3472: 3471: 3469: 3465: 3459: 3456: 3454: 3451: 3447: 3444: 3443: 3442: 3439: 3438: 3436: 3432: 3426: 3423: 3421: 3418: 3416: 3413: 3411: 3408: 3406: 3403: 3401: 3398: 3397: 3395: 3393: 3389: 3383: 3380: 3378: 3375: 3373: 3370: 3368: 3365: 3364: 3362: 3358: 3352: 3349: 3347: 3344: 3342: 3339: 3337: 3334: 3332: 3329: 3327: 3326:Counting sort 3324: 3322: 3319: 3317: 3314: 3312: 3309: 3307: 3304: 3303: 3301: 3297: 3291: 3288: 3286: 3283: 3281: 3278: 3276: 3273: 3272: 3270: 3266: 3260: 3257: 3255: 3252: 3250: 3247: 3245: 3242: 3240: 3237: 3235: 3232: 3231: 3229: 3225: 3219: 3216: 3214: 3211: 3209: 3206: 3204: 3201: 3199: 3196: 3194: 3191: 3189: 3186: 3185: 3183: 3181: 3177: 3171: 3168: 3166: 3163: 3161: 3158: 3156: 3153: 3151: 3150:Odd–even sort 3148: 3146: 3143: 3141: 3138: 3137: 3135: 3131: 3125: 3122: 3120: 3117: 3115: 3114:X + Y sorting 3112: 3110: 3107: 3105: 3102: 3100: 3099:Adaptive sort 3097: 3095: 3092: 3090: 3087: 3085: 3082: 3080: 3077: 3075: 3072: 3070: 3067: 3065: 3062: 3061: 3059: 3055: 3051: 3044: 3039: 3037: 3032: 3030: 3025: 3024: 3021: 3005: 2998: 2984:on 2016-12-20 2983: 2979: 2972: 2961: 2957: 2953: 2948: 2947: 2943: 2935: 2931: 2927: 2923: 2916: 2902: 2901: 2896: 2890: 2888: 2873:on 2014-04-15 2872: 2868: 2861: 2859: 2850: 2846: 2841: 2836: 2832: 2828: 2821: 2813: 2809: 2802: 2794: 2790: 2786: 2782: 2778: 2774: 2767: 2759: 2755: 2750: 2745: 2741: 2737: 2736: 2728: 2726: 2717: 2713: 2706: 2698: 2692: 2689: 2685: 2681: 2680: 2672: 2664: 2663: 2655: 2647: 2643: 2642: 2637: 2630: 2622: 2618: 2614: 2610: 2609: 2601: 2586: 2579: 2578: 2570: 2568: 2563: 2556: 2554: 2547:Disadvantages 2544: 2542: 2532: 2529: 2528:adaptive sort 2519: 2515: 2511: 2507: 2503: 2493: 2491: 2487: 2483: 2479: 2475: 2474:non-recursive 2465: 2448: 2442: 2434: 2418: 2414: 2410: 2390: 2386: 2382: 2362: 2358: 2354: 2334: 2330: 2326: 2302: 2298: 2295: 2292: 2286: 2265: 2261: 2258: 2250: 2245: 2228: 2222: 2200: 2176: 2151: 2145: 2123: 2099: 2088: 2072: 2048: 2023: 2017: 1995: 1971: 1946: 1935: 1918: 1912: 1887: 1882: 1877: 1872: 1869: 1863: 1841: 1817: 1792: 1786: 1764: 1752: 1735: 1729: 1707: 1701: 1695: 1688:in size, the 1673: 1663: 1644: 1638: 1615: 1611: 1607: 1604: 1599: 1595: 1588: 1565: 1561: 1557: 1554: 1549: 1545: 1538: 1513: 1509: 1502: 1492: 1482: 1471: 1468: 1465: 1464: 1463: 1455: 1453: 1448: 1445: 1440: 1437: 1433: 1429: 1425: 1421: 1403: 1399: 1395: 1391: 1387: 1383: 1379: 1375: 1371: 1361: 1358: 1357: 1353: 1350: 1349: 1345: 1340:(count + 1)/2 1336: 1335: 1331: 1328: 1327: 1323: 1320: 1319: 1316: 1313: 1311: 1306: 1297: 1294: 1285: 1282: 1278: 1272: 1268: 1263: 1257: 1249: 1241: 1233: 1229: 1225: 1221: 1215: 1208: 1205: 1201: 1197: 1193: 1189: 1185: 1178: 1177:MergeInternal 1174: 1165: 1163: 1159: 1155: 1154:floating hole 1150: 1148: 1144: 1140: 1133: 1130: 1126: 1125:MergeInternal 1122: 1115: 1111: 1107: 1100: 1094: 1090: 1084: 1080: 1070: 1067: 1063: 1059: 1044: 1041: 1037: 1036:MergeInternal 1033: 1023: 1016: 1009: 1002: 994: 990: 986: 973: 968: 965: 959: 956: 947: 941:Roll and drop 936: 932: 928: 914: 912: 874: 863: 858: 844: 826: 822: 812: 808: 769: 758: 754: 750: 746: 742: 738: 734: 726: 722: 715: 711: 707: 703: 697: 688: 684: 680: 673: 669: 665: 661: 660:InsertionSort 657: 647: 643: 639: 621: 617: 613: 606: 602: 599: 598: 595: 591: 587: 583: 576: 572: 569: 566: 565: 561: 558: 557: 556:Linear search 553: 550: 546: 542: 541: 540:Binary search 537: 534: 533: 529: 526: 525: 521: 520: 519: 512: 508: 505: 502: 501: 497: 494: 493: 490: 486: 482: 479: 476: 472: 468: 467: 464: 461: 458: 457: 454: 451: 448: 447: 444: 441: 438: 437: 434: 431: 428: 427: 424: 416: 396: 378: 369: 355: 335: 329: 318: 297: 287: 284:, where each 283: 273: 269: 265: 261: 255: 241: 225: 222: 218: 212: 208: 204: 200:to arrive at 199: 195: 191: 187: 183: 173: 169: 167: 164: 160: 155: 151: 147: 143: 141: 138: 134: 129: 125: 121: 119: 116: 112: 107: 103: 99: 95: 93: 90: 86: 83: 80: 76: 73: 70: 66: 35: 30: 22: 3510:Stable sorts 3399: 3392:Hybrid sorts 3341:Proxmap sort 3254:Library sort 3124:Quantum sort 3007:. Retrieved 3002:Tim Peters. 2997: 2986:. Retrieved 2982:the original 2971: 2942: 2925: 2921: 2915: 2904:. Retrieved 2898: 2875:. Retrieved 2871:the original 2830: 2826: 2820: 2807: 2801: 2772: 2766: 2739: 2733: 2711: 2705: 2678: 2671: 2661: 2654: 2645: 2639: 2629: 2612: 2606: 2600: 2589:. Retrieved 2576: 2550: 2540: 2538: 2525: 2516: 2512: 2508: 2505: 2489: 2471: 2246: 2244:complexity. 2089: 1936: 1753: 1494: 1480: 1461: 1449: 1443: 1441: 1435: 1431: 1427: 1423: 1419: 1401: 1397: 1393: 1389: 1385: 1381: 1377: 1373: 1369: 1367: 1314: 1309: 1307: 1303: 1295: 1291: 1288:Redistribute 1283: 1279: 1275: 1270: 1266: 1260: 1255: 1247: 1239: 1231: 1230:(|A| > 0 1227: 1224:MergeInPlace 1223: 1218: 1213: 1206: 1203: 1199: 1195: 1191: 1187: 1183: 1176: 1171: 1168:Local merges 1161: 1157: 1153: 1151: 1146: 1142: 1138: 1136: 1132:MergeInPlace 1131: 1128: 1124: 1120: 1113: 1109: 1098: 1092: 1088: 1082: 1078: 1068: 1065: 1061: 1057: 1043:MergeInPlace 1042: 1039: 1035: 1031: 1021: 1014: 1007: 1000: 992: 988: 984: 971: 963: 960: 954: 952: 934: 930: 926: 913:the blocks. 910: 891: 876:Tagging the 868:Tag A blocks 861: 842: 836: 831:integer_step 824: 810: 806: 774: 756: 752: 748: 744: 740: 736: 732: 724: 720: 713: 709: 705: 694: 686: 682: 678: 671: 667: 663: 659: 655: 645: 641: 629: 615: 611: 600: 593: 589: 585: 581: 570: 562: 554: 548: 544: 538: 530: 522: 517: 510: 509:-th item of 506: 488: 484: 474: 470: 422: 397: 376: 370: 353: 333: 327: 316: 298: 285: 279: 267: 263: 259: 256: 239: 210: 206: 202: 185: 181: 180: 171: 153: 149: 145: 127: 123: 105: 101: 97: 3474:Stooge sort 3316:Bucket sort 3268:Merge sorts 3140:Bubble sort 3084:Inplacement 3074:Total order 1631:, which is 1400:appears in 1240:BinaryFirst 1066:(see below) 1001:BinaryFirst 618:(this is a 443:shift right 398:Once every 340:block into 246:block into 140:performance 118:performance 92:performance 3499:Categories 3420:Spreadsort 3382:Samplesort 3346:Radix sort 3275:Merge sort 3213:Cycle sort 3198:Smoothsort 3160:Gnome sort 3009:2020-09-13 2988:2016-12-11 2906:2014-03-23 2877:2014-03-23 2591:2016-09-07 2559:References 2535:Advantages 2522:Adaptivity 2010:times, or 1485:Complexity 1418:values of 1256:BinaryLast 999:B_split = 626:Outer loop 532:Block swap 459:++ and += 433:bitwise OR 182:Block sort 163:Worst-case 89:Worst-case 27:Block sort 3415:Introsort 3351:Flashsort 3321:Burstsort 3311:Bead sort 3249:Tree sort 3244:Splaysort 3239:Shellsort 3170:Quicksort 3155:Comb sort 3089:Stability 2835:CiteSeerX 2793:0097-5397 2744:CiteSeerX 2496:Stability 2299:⁡ 2262:⁡ 1883:× 1660:once the 1605:× 1555:× 1452:quicksort 1214:BlockSwap 1184:BlockSwap 1089:BlockSwap 1008:BlockSwap 706:BlockSort 642:BlockSort 575:reversals 551:position. 487:and < 463:increment 439:>> 419:Algorithm 115:Best-case 3484:Bogosort 3479:Slowsort 3193:Heapsort 1477:Analysis 1376:, where 1300:Variants 1158:floating 1106:overflow 1064:minA = 964:dropping 276:Overview 221:in-place 3410:Timsort 2553:Timsort 2518:order. 2191:blocks 1413:√ 1406:√ 1374:s1 t s2 1338:√ 1099:minimum 1069:else if 935:minimum 911:tagging 829:√ 801:each), 796:√ 777:√ 749:else if 683:else if 594:Reverse 590:Reverse 586:Reverse 483:from ≥ 429:| 368:block. 325:√ 314:√ 254:pairs. 188:, is a 137:Average 47:√ 3057:Theory 2900:GitHub 2837: 2791: 2746: 2693: 2468:Memory 2247:After 1444:second 1324:Notes 1248:Rotate 1238:mid = 1079:Rotate 1022:Rotate 955:rolled 745:Rotate 679:Rotate 620:64-bit 582:Rotate 503:array 453:modulo 334:number 240:blocks 224:stable 3434:Other 3079:Lists 2581:(PDF) 2482:stack 1905:, or 1321:Size 1228:while 1188:while 1147:index 1143:index 1062:break 972:while 862:while 843:could 825:while 753:Merge 725:while 721:while 714:floor 687:Merge 605:floor 545:first 511:array 481:range 356:each 286:level 215:(see 194:merge 184:, or 82:Array 68:Class 2789:ISSN 2691:ISBN 1442:The 1422:and 1380:and 1351:512 1343:+ 1 1207:Swap 1204:else 1200:Swap 1162:hole 1152:The 1129:else 1114:else 1083:else 1040:else 1015:Swap 931:Swap 896:and 849:and 807:last 634:and 549:last 524:Swap 410:and 402:and 303:and 292:and 266:log 230:and 209:log 152:log 104:log 2930:doi 2845:doi 2781:doi 2754:doi 2740:237 2646:186 2617:doi 2419:128 2296:log 2259:log 1581:to 1267:for 1232:and 1192:and 989:and 927:for 837:If 813:of 811:end 668:for 664:for 656:for 174:(1) 52:= 4 3501:: 2926:35 2924:. 2897:. 2886:^ 2857:^ 2843:. 2831:38 2829:. 2810:. 2787:. 2775:. 2752:. 2738:. 2724:^ 2714:. 2686:- 2613:18 2611:. 2583:. 2566:^ 2464:. 2403:, 2391:64 2375:, 2363:32 2335:16 1934:. 1751:. 1616:31 1596:31 1566:16 1546:16 1424:s2 1420:s1 1402:s1 1398:s2 1394:s1 1390:s1 1382:s2 1378:s1 1359:0 1271:if 1196:if 1121:if 1110:if 1093:if 1058:if 1032:if 993:or 985:if 757:if 741:if 737:if 733:if 702:: 672:if 616:if 603:: 477:) 473:, 449:% 252:AB 219:) 49:16 3042:e 3035:t 3028:v 3012:. 2991:. 2954:. 2936:. 2932:: 2909:. 2880:. 2851:. 2847:: 2795:. 2783:: 2760:. 2756:: 2623:. 2619:: 2594:. 2490:n 2452:) 2449:n 2446:( 2443:O 2415:/ 2411:n 2387:/ 2383:n 2359:/ 2355:n 2331:/ 2327:n 2307:) 2303:n 2293:n 2290:( 2287:O 2266:n 2232:) 2229:n 2226:( 2223:O 2201:A 2177:A 2155:) 2152:n 2149:( 2146:O 2124:A 2100:A 2073:A 2049:A 2027:) 2024:n 2021:( 2018:O 1996:A 1972:A 1947:A 1922:) 1919:n 1916:( 1913:O 1893:) 1888:n 1878:n 1873:+ 1870:n 1867:( 1864:O 1842:A 1818:A 1796:) 1793:n 1790:( 1787:O 1765:A 1739:) 1736:n 1733:( 1730:O 1708:2 1702:n 1696:O 1674:A 1648:) 1645:n 1642:( 1639:O 1619:) 1612:/ 1608:n 1600:2 1592:( 1589:O 1569:) 1562:/ 1558:n 1550:2 1542:( 1539:O 1519:) 1514:2 1510:n 1506:( 1503:O 1432:j 1428:i 1415:A 1408:A 1386:t 906:B 902:A 898:B 894:A 886:B 882:A 878:A 855:A 851:B 847:A 839:B 819:B 815:B 803:B 798:A 792:A 788:A 784:A 779:A 636:B 632:A 577:. 507:i 489:y 485:x 475:y 471:x 469:[ 412:B 408:A 404:B 400:A 393:B 389:A 385:A 381:A 373:A 366:A 362:B 358:A 350:B 346:A 342:B 338:A 328:A 317:A 309:A 305:B 301:A 294:B 290:A 270:) 268:n 264:n 262:( 260:O 248:B 244:A 236:A 232:B 228:A 213:) 211:n 207:n 205:( 203:O 172:O 156:) 154:n 150:n 148:( 146:O 130:) 128:n 126:( 124:O 108:) 106:n 102:n 100:( 98:O 60:B 56:A 42:A 23:.

Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.

Index