greeNsort® Glossary: algorithm briefs

For a systematic classification of the algorithms briefly described here¹ see the portfolio section.

Bimesort

Bimesort is our name for a prior-art nocopy-Mergesort that uses merging with one loop-check via a sentinel as described by Robert Segdewick under the somewhat ambiguous name Bitonic Mergesort. The trick is to sort the left branch ascending and the right branch descending (or vice versa), then the merge from outer to inner ends until pointers cross which requires only one termination-check per loop traversal. The algorithm as described by Sedgewick is not stable, the greeNsort^® implementation is stable. For a simpler algorithm with one loop-check see Knuthsort.

Copysort

Copysort is our name for a naive copy-Mergesort that copies both input streams to 100% buffer and merges back (or vice versa). For a better approach that only merges without copying see Mergesort.

Dupisort

Dupisort is our name for Yaroslavskiy’s prior-art Dual-Pivot-Quicksort which makes better use of the extra-operations invested for adaptivity than Quicksort3: it generates three full partitions instead of two plus ties, and hence is \(\mathcal{O}(N\log_3{N})\) instead of \(\mathcal{O}(N\log_2{N})\), but it is inherently serial. The implementation of Yaroslavskiy contains a redundant branch, for a slightly faster implementation without this redundant branch see Tricksort. For the prior-art Block-Quicksort algorithm that is simpler and faster (but not adaptive) see Quicksort2B, for a greeNsort^® algorithm that is simpler, faster and as adaptive see ZacksortB.

Ducksort

Ducksort is a greeNsort^® algorithm that enhances Zucksort with \(\mathcal{O}(N)\) adaptivity to presorted data. For the faster block-tuned version see DucksortB

DucksortB

DucksortB is a greeNsort^® version of Ducksort that is block-tuned to reduce branch-misprediction and hence as fast but more adaptive than Quicksort2B, Quicksort3 and Dupisort.

Frogsort

Frogsort² is a greeNsort^® algorithm that achieves the advantages of Knuthsort with only 50% buffer. Frogsort is automatically adaptive to presorted data and can be further tuned for more adaptive merges. For a variant that is automatically adaptive to presorted and reverse-sorted data see Geckosort. For an algorithm that is faster tuned adaptive to presorted and reverse-sorted data see Squidsort. For algorithms that sort size-varying elements see VFrogsort1 and XFrogsort1.

Frogsort0

Frogsort0 is the initial root version of Frogsort that uses 50% buffer.

Frogsort1

Frogsort1 is the standard version of Frogsort that uses 50% buffer.

Frogsort2

Frogsort2 is a version of Frogsort tuned to use less than 50% buffer. For sorting doubles we found a sweet spot of 14% buffer, and despite using less memory it is significantly faster than Frogsort (and Knuthsort).

Frogsort3

Frogsort3 is a version of Frogsort tuned to use less than 50% buffer. For sorting doubles we found a sweet spot of 12% buffer.

Geckosort

Geckosort³ is a greeNsort^® variant of Frogsort that is automatically adaptive to presorted and reverse-sorted data. For an algorithm that is faster tuned adaptive to presorted and reverse-sorted data see Squidsort.

Grailsort

Grailsort is an excellent implementation by Andrey Astrelin (2014) of an inplace-merge algorithm of Huang&Langston (1989-1992), such that it was just about 1.5 times slower than standard Mergesort. This was a huge achievement over the classic inplace-mergesort of Dudzinski&Dydek (1981) which was about 5 times slower than Mergesort. For a version that is somewhat faster by using \(\sqrt{N}\) buffer see Sqrtsort. For an greeNsort^® algorithm needing negligible buffer that is almost as fast as Mergesort see Walksort.

Heapsort

Heapsort is old inplace sorting algorithm with \(\mathcal{O}(N\log{N})\) worst-case, but not stable and not fast, due to wild random access: it first build a heap inplace, than removes one minimum (or maximum) value after the other, again inplace, for details see Wikipedia. Usually Quicksort is preferred for its faster average case \(\mathcal{O}(N\log{N})\) runtime, however, sometimes Heapsort is used as a fallback in Quicksort, see Introsort.

Ininsort

Ininsort is our name⁴ for a prior-art nocopy-Mergesort that can merge with 50% buffer only as described by H. W. Lang. It uses two loop-checks, for a version with one loop-check see Ninisort. Ininsort is inherently serial, for an equally good greeNsort^® algorithm that can be parallelized see Frogsort.

Introsort

Introsort is a combination of Quicksort2 or Quicksort3 with Heapsort as a fallback against quadratic runtime: if the Quicksort reaches a too deep recursion level, the Introsort switches to Heapsort. Note that a properly designed Zacksort with random pivots has a probabilistic convergence guarantee such that the expected runtime never gets better by switching to Heapsort.

IS4o

IS4o (short for Inplace-Super-Scalar-Sample-Sort) is the serial version of IPS4o. It is not stable, complicated and slower than Pdqsort.

IPS4o

IPS4o (short for Inplace-Parallel-Super-Scalar-Sample-Sort) has been designed by Axtmann, Witt, Ferizovic & Sanders (2017) as a superior multicore replacement for slower implementations of sorting APIs. As a k-ary comparison sort it’s performance is theoretically faster than binary-algorithms and slower than radix-algorithms such as Skasort (if implemented in parallel). The library is very fast, however, the algorithm is not stable and at least the serial version IS4o does not hold the speed promise: Pdqsort is faster. However, since Pdqsort like all Quicksort is difficult to parallelize, IPS4o might beat a parallel Pdqsort (or ZacksortB).

Jumpsort

Jumpsort is greeNsort^® variation of Walksort which can be faster in certain machines.

Katasort

Katasort is our name for a prior-art nocopy-Mergesort that uses merging with a half loop-check as described by Jyrki Katajainen. The trick is to invest one comparison before merging in order to find out which of the two input sequences exhausts first, the the merge-loop only needs to check for termination if the element is taken from this sequence, this happens on average every second loop traversal. For further information see A Meticulous Analysis of Mergesort Programs. For faster k-ary versions see Katasort3 and Katasort4.

Katasort3

Katasort3 is a 3-ary version of Katasort.

Katasort4

Katasort4 is a 4-ary version of Katasort.

Kiwisort

Kiwisort is a stable greeNsort^® algorithm using 100% buffer that is adaptive to ties (\(\mathcal{O}(N\log{D})\) average case). It uses uses distant buffer. For a similar algorithm that uses buffer-partitioning hence minimizes distances, see Swansort.

Knuthsort

Knuthsort is a prior-art nocopy-Mergesort that uses merging with one loop-check as described by Donald Knuth in The Art of Computer Programming. The trick in merging is to check only that sequence for termination from which the last elements has been taken. Knuthsort serves as a the standard reference for stable equally-sized generic sorting but it requires 100% buffer. For faster k-ary versions see Knuthsort3 and Knuthsort4. For a equally good algorithm that sorts with 50% buffer see Frogsort. Knuthsort can be tuned to reduce comparisons from \(\mathcal{O}(N\log{N})\) to \(\mathcal{O}(N)\) for presorted data, but movements still make the best case \(\mathcal{O}(N\log{N})\), for a equally good algorithm with a \(\mathcal{O}(N)\) best case see Omitsort.

Knuthsort3

Knuthsort3 is a 3-ary version of Knuthsort.

Knuthsort4

Knuthsort4 is a 4-ary version of Knuthsort.

Mergesort

Mergesort is a prior-art generic sorting algorithm that that uses balanced split&merge, for further information see wikipedia. We use the term as an umbrella for nocopy-Mergesorts that - unlike Timsort - just merge without extra copying, for different implementations with 100% buffer see Nocosort, Bimesort, Knuthsort and Katasort, for serial versions with 50% buffer see Ininsort and Ninisort; for an equally good algorithm that can be parallelized with 50% buffer see Frogsort.

MFrogsort2

MFrogsort2 is version of Frogsort2 that sorts long records with short keys: it sorts columns of matrices by keys in the first row. See NFrogsort2 for a version that sorts keys separated from payload and finally reorders payload. For a less sustainable algorithm, see MKnuthsort.

MKnuthsort

MKnuthsort is version of Knuthsort that sorts long records with short keys: it sorts columns of matrices by keys in the first row. See NKnuthsort for a version that sorts keys separated from payload and finally reorders payload. For a more sustainable algorithm, see MFrogsort2.

NFrogsort2

NFrogsort2 is version of Frogsort2 that sorts short keys separated from long records: it sorts columns of matrices by keys in the first row. See MFrogsort2 for a version that moves payload together with keys. For a less sustainable algorithm, see NKnuthsort.

NKnuthsort

NKnuthsort is version of Knuthsort that sorts short keys separated from long records: it sorts columns of matrices by keys in the first row. See MKnuthsort for a version that moves payload together with keys. For a more sustainable algorithm, see NFrogsort2.

Nocosort

Nocosort is a prior-art nocopy-Mergesort that uses merging with a triple loop-check as described by Robert Sedgewick in Algorithms in C. It is Sedgewick’s strawman for introducing Bimesort with just one loop-check, but actually Donald Knuth had described much earlier and easier how to merge with just one loop-check, see Knuthsort.

Natural-Mergesort

Natural-Mergesort is a prior-art generic sorting algorithm that tries to find sorted runs in the input. It is adaptive to presorted data at the expense of imbalanced merging and hence slower if data is not completely unsorted. For further information see wikipedia. For real world implementations see Timsort, Peeksort and Powersort. For a superior approach to sorting see Mergesort.

Ninisort

Ninisort is a variant⁵ of Ininsort with ony one loop-check as teached by Donald Knuth see Knuthsort. Ninisort is inherently serial, for an equally good greeNsort^® algorithm that can be parallelized see Frogsort.

Omitsort

Omitsort is a greeNsort^® algorithm which proves that a \(\mathcal{O}(N)\) best case for presorted data is possible without accepting the slower speed of Timsort. For an algorithm that is equally adaptive also to reverse-sorted data, see Octosort.

Octosort

Octosort greeNsort^® improvement over Omitsort that provides a \(\mathcal{O}(N)\) best case for presorted and refverse-sorted data. It still requires 100% buffer, for a bidirectionally adaptive algorithm that sorts with 50% buffer see Squidsort.

Pdqsort

Pdqsort (short for Pattern-Defeating-Quicksort) from Orson Peters (2015) is a Quicksort that comes close to Zacksort regarding theoretical speed (like Quicksort2B ) and adaptivity for ties (like Quicksort3). It is further tuned with Insertionsort2 which makes it adaptive for presorted data and slower for expensive comparison functions. The very professional C++ implementation on github even outperforms IS4o. Pdqsort theoretically needs more operations than Zacksort, for an empirical judgement comparable implementations would be needed.

Peeksort

Peeksort is a prior-art sorting algorithm engineered by J. Ian Munro and Sebastian Wild. It is a Natural-Mergesort designed to be extremely adaptive for almost perfectly presorted data but faster than Timsort. Its a clever top-down algorithm optimizing split points by searching along presorted seqences but suffers like Timsort and Powersort from inefficient copying with merging. For further information see online. For an algorithm that is faster in hard sorting tasks see Squidsort.

Powersort

Powersort is a prior-art sorting algorithm engineered by J. Ian Munro and Sebastian Wild. It is a Natural-Mergesort designed to be extremely adaptive for almost perfectly presorted data but faster than Timsort. Its a more light-weight bottom-up algorithm like Timsort but suffers like that and Peeksort from inefficient copying with merging. For further information see online. For an algorithm that is faster in hard sorting tasks see Squidsort.

PDucksort

PDucksort is a branch-parallel version of Ducksort, see also PQuicksort2 and PKnuthsort.

PDucksortB

PDucksortB is a block-tuned version of PDucksort, see also DucksortB and PQuicksort2B.

PFrogsort0

PFrogsort0 is a full-parallel version of Frogsort0, see also PFrogsort1 and PKnuthsort.

PFrogsort1

PFrogsort1 is a almost full-parallel version of Frogsort1, the setup-phase is not parallel, see also PFrogsort0 and PFrogsort2.

PFrogsort2

PFrogsort2 is a almost full-parallel version of Frogsort2, the setup-phase is not parallel, see also PFrogsort1 and PFrogsort3.

PFrogsort3

PFrogsort3 is a almost full-parallel version of Frogsort3, the setup-phase is not parallel, see also PFrogsort2.

PKnuthsort

PKnuthsort is a full-parallel version of Knuthsort, see also PFrogsort0 and PDucksort.

Quicksort

Quicksort algorithms are a class of unstable inplace partitioning algorithms with a good average \(\mathcal{O}(N\log{N})\) runtime.

Quicksort1

Quicksort1 is our name for the original adaptive but binary Quicksort of Hoare (1961) where two pointers are moved outside-in with with an attempt to isolate pivot-ties. It is not reliable, see Quicksort2 for a reliable non-adaptive version and Quicksort3 for a reliable adaptive but more expensive version. For a greeNsort^® algorithm that is fast, adaptive to ties and reliable see Zacksort.

Quicksort2

Quicksort2 is our name for the prior-art non-adaptive binary Quicksort of Singleton (1969) recommended by Sedgewick (1977) where two pointers are moved outside-in with stop and swap on ties. It is less adaptive to ties than Quicksort3, for the faster block-tuned version see Quicksort2B. For a greeNsort^® algorithm that is equally fast but adaptive to ties see Zacksort.

Quicksort2B

Quicksort2B is our name for the prior-art non-adaptive binary Block-Quicksort of Edelkamp&Weiß (2016) which is based on Quicksort2 but reduces branch-misprediction. For a greeNsort^® algorithm that is equally fast but adaptive to ties see ZacksortB.

Quicksort3

Quicksort3 is our name for the prior-art adaptive ternary Quicksort of Bentley&McIlroy (1993) which partitions into two full partitions plus a tie-partition. Due to extra operations for tie-detection and movement it is slower than Quicksort2. For the better prior-art adaptive Dual-Pivot-Quicksort see Dupisort, for a greeNsort^® algorithm that is equally adaptive but faster see Zacksort.

Quickpartial

Quickpartial is our name for a simplified application of Quicksort2 for partial sorting: after selection of k, the element is in the k-th position, which would be in the k-th position had the data be sorted completely, furthermore all elements with keys lower than the key of k are at the positions below k (completely sorted), all elements with keys greater than the key of k are at the positions above k (but not sorted). See also Quickselect and for superior algorithms Zackpartial and Zuckpartial.

Quickselect

Quickselect is a simplified application of Quicksort2 for selection: after selection of k, the element is in the k-th position, which would be in the k-th position had the data be sorted completely, furthermore all elements with keys lower than the key of k are at the positions below k (not sorted), all elements with keys greater than the key of k are at the positions above k (not sorted). See also Quickpartial and for superior algorithms Zackselect and Zuckselect.

Skasort

Skasort is prior-art example of a API and implementation for sorting with radix-algorithms suggested by Malte Skarupke (2015). For atomic data types and strings radix-algorithms can be substantially faster (and more sustainable) than the other, more generic comparison based algorithms in this glossary. Note that (MSB)radix-algorithms can be made adaptive to ties, but are typically less adaptive to presorting.

Sqrtsort

Sqrtsort is prior-art algorithm of Andrej Astrelin that is somewhat faster than his inplace Grailsort by using \(\sqrt{N}\) buffer. For a greeNsort^® algorithm that is much faster see Walksort.

Squidsort

Squidsort is a greeNsort^® improvement over Frogsort that is tuned adaptive to presorted and reverse-sorted data see Squidsort. Squidsort is faster and more sustainable than Timsort in almost every situation, see the results section.

Squidsort1

Squidsort1 is the standard variant of Squidsort that uses 50% buffer.

Squidsort2

Squidsort2 is a variant of Squidsort tuned to use less than 50% buffer. For sorting doubles we found a sweet spot of 14% buffer, and despite using less memory it is significantly faster than Frogsort (and Knuthsort).

Swansort

Swansort is a stable greeNsort^® algorithm using 100% buffer that is adaptive to ties (\(\mathcal{O}(N\log{D})\) average case). It uses buffer-partitioning hence minimizes distances. For a similar algorithm that uses distant buffer, see Kiwisort.

Timsort

Timsort is a prior-art sorting algorithm engineered by Tim Peters for use a standard-library-sort in the Python language. It is a Natural-Mergesort tuned to be extremely adaptive for almost perfectly presorted data, for further information see wikipedia. Timsort is known to be quite slow for truly unsorted data, see the results section. For an algorithm that is faster in almost all situations see Squidsort.

Tricksort

Tricksort is an slightly faster version of Dupisort that omits a redundant branch. For the prior-art Block-Quicksort algorithm that is simpler and faster (but not adaptive) see Quicksort2B, for the greeNsort^® algorithm that is simpler, faster and as adaptive see ZacksortB.

Walksort

Walksort is a greeNsort^® algorithm that works with only \(\sqrt{N}\) buffer, is almost as fast as Mergesort and that is much faster than Sqrtsort. For a variation see Jumpsort.

UZacksort

UZacksort is a greeNsort^® variant of Zacksort that sorts pointers to size-varying elements. For a slower stable algorithm see WQuicksort2⁶, for algorithms that directly sort size-varying elements without random access see VFrogsort1 and XFrogsort1.

XFrogsort1

XFrogsort1 is a greeNsort^® variant of Frogsort1 that sorts size-varying elements together with references to them. For an algorithm that sorts size-varying elements without references see VFrogsort1.

XSwansort

XSwansort is a greeNsort^® variant of Swansort that sorts size-varying elements together with references to them. For an algorithm that sorts size-varying elements without references see VSwansort.

VFrogsort1

VFrogsort1 is a greeNsort^® variant of Frogsort1 that sorts size-varying elements that do not contain a separator (sorting string separated by a null-string-terminator). For an algorithm that can sort arbitrary size-varying elements see XFrogsort1.

VSwansort

VSwansort is a greeNsort^® variant of Swansort that sorts size-varying elements that do not contain a separator (sorting string separated by a null-string-terminator). For an algorithm that can sort arbitrary size-varying elements see XSwansort.

WQuicksort2

WQuicksort2 is a variant of Quicksort2 that sorts pointers to size-varying elements and achieves stability by breaking ties by pointer values. For an algorithm that adjusts to ties see UZacksort, for algorithms that directly sort size-varying elements without random access see VFrogsort1 and XFrogsort1.

Zacksort

Zacksort is a greeNsort^® algorithm that combines the speed of Quicksort2 with the adaptivity of Quicksort3. For a variation see Zucksort and for a block-tuned version that reduces branch-misprediction see ZucksortB. For a version that sorts pointers to size-varying elements see UZacksort.

ZacksortB

ZacksortB is a greeNsort^® version of Zacksort that is block-tuned to reduce branch-misprediction and hence as fast but more adaptive than Quicksort2B and as adaptive but faster than Dupisort.

Zucksort

Zucksort is a greeNsort^® variation of Zacksort that might be slightly faster on certain systems. For an algorithm that is not only \(\mathcal{O}(N\log{D})\) adaptive to ties but also \(\mathcal{O}(N)\) adaptive to presorted data see Ducksort.

ZucksortB

ZucksortB is a greeNsort^® version of Zucksort that is block-tuned to reduce branch-misprediction and hence as fast but more adaptive than Quicksort2B and as adaptive but faster than Dupisort.

Zackpartial

Zackpartial is our name for a simplified application of *Zacksort for partial sorting: after selection of k, the element is in the k-th position, which would be in the k-th position had the data be sorted completely, furthermore all elements with keys lower than the key of k are at the positions below k (completely sorted), all elements with keys greater than the key of k are at the positions above k (but not sorted). See also Zuckpartial, Zackselect and for an inferior algorithm Quickpartial.

Zackselect

Zackselect is a simplified application of Zacksort for selection: after selection of k, the element is in the k-th position, which would be in the k-th position had the data be sorted completely, furthermore all elements with keys lower than the key of k are at the positions below k (not sorted), all elements with keys greater than the key of k are at the positions above k (not sorted). See also Zuckselect, Zackpartial and for an inferior algorithm Quickselect.

Zuckpartial

Zuckpartial is our name for a simplified application of *Zacksort for partial sorting: after selection of k, the element is in the k-th position, which would be in the k-th position had the data be sorted completely, furthermore all elements with keys lower than the key of k are at the positions below k (completely sorted), all elements with keys greater than the key of k are at the positions above k (but not sorted). See also Zackpartial, Zuckselect and for an inferior algorithm Quickpartial.

Zuckselect

Zuckselect is a simplified application of Zucksort for selection: after selection of k, the element is in the k-th position, which would be in the k-th position had the data be sorted completely, furthermore all elements with keys lower than the key of k are at the positions below k (not sorted), all elements with keys greater than the key of k are at the positions above k (not sorted). See also Zackselect, Zuckpartial and for an inferior algorithm Quickselect.

The only place success comes before work is in the dictionary ― Vince Lombardi

This glossary contains only the most important new and prior-art algorithms implemented in the greeNsort^® testbed↩︎
FROG is an acronym describing the core innovation of Frogsort (and Geckosort): Flip Recursive Organized Gaps↩︎
The Gecko is not only left-right-symmetric but also a rear-front-symmetric relative of the Frog↩︎
‘Inin’ is an acronym for ‘Inplace’ and ‘Into’, the two central functions in Ininsort↩︎
‘Nini’ sounds like the German ‘Nie nie’ which means ‘never ever’ do more loop checks than needed↩︎
since a stable Quicksort has no ties by definition a WZacksort would be unnecessarily complex and the simpler WQuicksort2 is sufficient↩︎