Project glossary

Glossary

Andrey Astrelin - A Russian mathematician and computer programmer; the original author of Grailsort

Array rotation - Shifts a portion of the array a certain number of steps to the left or the right. Here's a visual representation of rotating an array two spaces to the left: https://www.cs.southern.edu/halterman/Courses/Winter2011/124/Labs/ArrayManipulations/circulararray.png

Bentley's Juggling algorithm - an implementation of array rotations (see above) that uses gapped overwrites, similar to Shellsort. Performs an optimal number of writes compared to other rotation algorithms, but unfortunately has horrible cache (see below) performance due to jumping all around the array. Very slow on modern computers, albeit a very clever solution to the problem it's solving; used by team member thatsOven's "low-writes" variant of their own block merge sort, Heliumsort, and during certain circumstances in the Rust programming language library

Binary search left - a binary search that finds the first copy of an item (in sorted order, it would be closer to the left side of the array)

Binary search right - a binary search that finds the last copy of an item (in sorted order, it would be closer to the right side of the array)

Block - a subarray of size O(sqrt n) which breaks up larger subarrays into chunks that can easily be rearranged and merged in optimal O(n) time

Block Merge Sort - a collection of similar "blueprints" that extensively use the idea of O(sqrt n)-sized blocks to create a stable, in-place, O(n log n) worst-case sorting algorithm. Both Grailsort and Wikisort are implementations of Block Merge Sort. Also known as "block sort"; see here for more information: https://en.wikipedia.org/wiki/Block_sort

Block swap - simple loop that swaps two chunks of an array, usually blocks. The chunks don't have to be right next to each other (adjacent), unlike array rotations

Block select(ion) sort - the portion of Grailsort used during Combine Blocks phase (see above) which rearranges the blocks of both subarrays being merged in sorted order by their heads; an O(sqrt n)-gapped selection sort with O(n) swaps

Build Blocks - the first few steps of Grailsort following Collect Keys (see below) where subarrays are merged together with the scrolling buffer without having to break them apart into blocks and rearranging them -- in other words, the subarrays are small enough to fit into the O(sqrt n)-sized scrolling buffer, making each subarray a "mini-block". Arguably one of the fastest parts of Grailsort, which basically boils down to a pretty straightforward in-place bottom-up merge sort

Buffer redistribution - the final phase of Grailsort which takes all the keys used during Grailsort and puts them back into the array via lazy merging

Buffer reset - the last step of "combine blocks" which brings the scrolling buffer all the way back to the beginning of the array. Costs O(n) swaps; removing buffer resets will be the main improvement featured in Holy Grail Sort

Buffer rewind - the portion of "smart merges" (see below) that moves the scrolling buffer backwards behind the remainder of a left subarray block. This is used to continue an ongoing merge that has run out of buffer space if the left blocks still has items to merge; costs O(sqrt n) swaps in the absolute worst-case

Cache - a special part of computer memory which is extremely fast but only comes into play if the next steps of your code are easy to predict! It's a little bit technical, but you can learn more about computer cache here: http://web.cecs.pdx.edu/~jrb/cs201/lectures/cache.friendly.code.pdf

Collect Keys - the first portion of Grailsort which sifts through the array for keys to add to the key-buffer; stops when Grailsort either has found 2 sqrt n keys or has reached the end of the array

Combine Blocks - the largest portion (usually) of Grailsort following Build Blocks (see above) which takes over when subarrays to merge can no longer fit into the scrolling buffer. This means each subarray is bigger than a single block, so Grailsort now has to break apart the subarrays to merge into blocks and rearrange them before the scrolling buffer can optimally merge everything together. Perhaps the part of Grailsort which needs the most optimizations for Holy Grail

Common Sort - the main function of Grailsort that controls the entire algorithm

Dynamic (buffer) - refers to either a) external memory whose size depends on the size of the array or b) running Grailsort with a dynamic external buffer (O(sqrt n) items)

Fast Stable Merging and Sorting in Constant Extra Space - the name of the paper mentioned below with Huang-Langston

Gries-Mills - an implementation of array rotations (see above) that uses block swaps. Has good cache performance and is generally efficient; arguably the best rotation algorithm for modern computers. Used by Grailsort

Head - the first item of a block; used to sort blocks during block selection sort

Head order - The order of blocks from smallest to largest head

Huang-Langston - the original academic/research paper Grailsort is based off of, referred to by the paper's author's names

Key - A unique item found in the array used either to track the original order of equal items or to provide buffer space for in-place merging

Key-buffer - a collection of up to O(sqrt n) keys one after the other (contiguous) used to do work throughout Grailsort, such as tracking the original order of equal items. May or may not include the keys used for the scrolling buffer based on context. The key-buffer excluding the scrolling buffer (the left half; the scrolling buffer being the right half) is kept at the very beginning of the array for the majority of the algorithm

Lazy merge - a simple in-place merge used during buffer redistribution (see above) and Lazy Stable Sort which uses binary searches and array rotations instead of the scrolling buffer

Lazy Stable Sort - a simple in-place bottom-up merge sort that exclusively uses lazy merges (see right above). Grailsort will resort to Lazy Stable Sort if Collect Keys finds less than 4 keys in the array

Median key/midkey - the middle key in the sorted key-buffer (left half) used to track the original order of equal items. When Grailsort is smart merging two subarrays during Combine Blocks, the block next to the scrolling buffer came from the left subarray if its key is less-than the median key; otherwise, it came from the right subarray. Used to be called "midkey" in Grailsort's original implementation

Merge blocks - the portion of "combine blocks" after block selection sort which controls the smart merging (see below) of blocks

Optimized Gnomesort - another name for the variant of Insertion Sort vanilla Grailsort uses (swaps instead of overwrites)

Pairwise swaps - Grailsort's process of sorting pairs with swaps during Build Blocks (a.k.a. the first "level"/step of merging)

Pairwise writes - Grailsort's process of sorting pairs with writes during Build Blocks (a.k.a. the first "level"/step of merging)

Rewritten Grailsort - a much more intuitive and readable version of Grailsort rewritten by our Holy Grail Sort Project team

Rotate/rotation - see "array rotation"

Scrolling buffer - an in-place buffer that scrolls through the array, merging blocks as it goes and serving as space for items waiting to be merged; arguably the main feature of Grailsort. Since the items inside the buffer are keys (all unique), the buffer can safely be scrambled while merging without breaking stability. This buffer happens to be the right half of the (entire) key-buffer; the left half remains stationary. Other names include the "merge buffer", the "coalescing buffer", the "working buffer", and the "junk buffer"

Smart block select(ion sort) - an improvement on Grailsort's "block selection sort" (see above) devised by Holy Grail Sort Project team members, reducing the number of comparisons needed by recognizing each subarray is already in sorted order; only blocks swapped out of the way to make room for the next block in-order need to be checked. Saves an average of O(n log n) comparisons

Smart merge - Grailsort's merge during Combine Blocks after block selection sort; utilizes the median key to keep track of the original order of equal items and tracks the order and size of the remaining block when one of them has run out of items to merge

Smart lazy merge - a freaky... freakish... funky? combination between a smart merge and a lazy merge (see above) which does not use a scrolling buffer

Static (buffer) - refers to either a) external memory whose size doesn't dependent on the size of the array or b) running Grailsort with a static external buffer (512 items)

Strategy 1 - The fastest/most optimal mode of Grailsort, exclusively calling smart merges with a full scrolling buffer during Combine Blocks; rearranges blocks before merging with block selection sort. Used when Collect Keys finds at least 2 sqrt n keys in the array (the ideal amount)

Strategy 2 - The slowest/least optimal mode of Grailsort, calling smart merges with a partial scrolling buffer as long as blocks can fit inside the scrolling buffer, and then reverting to smart lazy merges for the remainder of the sort; rearranges blocks before merging with block selection sort. Used when Collect Keys finds less than 2 sqrt n keys in the array, but still manages to find at least 4 keys

Strategy 3 - The most simple mode of Grailsort, resorting only to Lazy Stable Sort (see above); unlike Strategy 1 & 2, Strategy 3 does not rearrange any blocks with block selection sort. Used when Collect Keys can't even find 4 keys in the array

Subarray - one of two portions of the array that will be included in a merge

Tail - the last item of a block; will be used to sort blocks for backwards smart merges in Holy Grail

Tail order - the order of blocks from smallest to largest tail

Three-reversal rotations - an implementation of array rotations (see above) that uses three reversals. Has good cache performance but is not as efficient as Gries-Mills; some consider this the "easiest" rotation to implement and intuit. Used by many C++ implementations of std::rotate for bidirectional iterators

Wikisort - Another implementation of Block Merge Sort; a more popular and much more adaptive rival to Grailsort. See https://github.com/BonzaiThePenguin/WikiSort for more info