- Bimesort
- Copysort
- Dupisort
- Frogsort
- Frogsort1
- Frogsort2
- Geckosort
- Grailsort
- Heapsort
- Ininsort
- Introsort
- IS4o
- IPS4o
- Jumpsort
- Katasort
- Katasort3
- Katasort4
- Knuthsort
- Knuthsort3
- Knuthsort4
- Mergesort
- Nocosort
- Natural-Mergesort
- Ninisort
- Omitsort
- Octosort
- Pdqsort
- Quicksort
- Quicksort2
- Quicksort2B
- Quicksort3
- Skasort
- Sqrtsort
- Squidsort
- Squidsort1
- Squidsort2
- Swansort
- Timsort
- Tricksort
- Walksort
- UZacksort
- XFrogsort1
- XSwansort
- VFrogsort1
- VSwansort
- WQuicksort2
- Zacksort
- ZacksortB
- Zucksort
- ZucksortB

For a systematic classification of the algorithms briefly described here^{1} see the portfolio section.

*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 Sedwick is *not stable*, the *greeNsort ^{®}* implementation

*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* is our name for Yaroslavskyi’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 Yaroslavskyi 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

*Frogsort* is a *greeNsort ^{®}* algorithm that achieves the advantages of

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

*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*).

*Geckosort* is a *greeNsort ^{®}* variant of

*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

*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* is our name^{2} 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

*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* (short for *Inplace-Super-Scalar-Sample-Sort*) is the serial version of *IPS4o*. It is *not stable, complicated and slower* than *Pdqsort*.

*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*).

*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* is a 3-ary version of *Katasort*.

*Katasort4* is a 4-ary version of *Katasort*.

*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* is a 3-ary version of *Knuthsort*.

*Knuthsort4* is a 4-ary version of *Knuthsort*.

*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*.

*Nocosort* is a prior-art nocopy-*Mergesort* that uses merging with a *triple loop-check* as described by Rober Sedgewick in *Algorithms in C*. It is Sedgewicks 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* 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 a *superior approach to sorting* see *Mergesort*.

*Ninisort* is a variant^{3} of *Ininsort* with ony one loop-check as teached by Donald Knuth see *Knuthsort*. *Ninisort* is inherently *serial*, for an *equally good greeNsort ^{®}* algorithm

*Omitsort* is a *greeNsort ^{®}* algorithm which proves that a

*Octosort* *greeNsort ^{®}* improvement over

*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.

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

*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

*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

*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

*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* 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

*Squidsort* is a *greeNsort ^{®}* improvement over

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

*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* is a stable *greeNsort ^{®}* algorithm using 100% buffer that is adaptive to ties (\(\mathcal{O}(N\log{D})\) average case). For versions

*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* 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

*Walksort* is a *greeNsort ^{®}* algorithm that works with only \(\sqrt{N}\) buffer, is almost as fast as

*UZacksort* is a *greeNsort ^{®}* variant of

*XFrogsort1* is a *greeNsort ^{®}* variant of

*XSwansort* is a *greeNsort ^{®}* variant of

*VFrogsort1* is a *greeNsort ^{®}* variant of

*VSwansort* is a *greeNsort ^{®}* variant of

*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* is a *greeNsort ^{®}* algorithm that combines the speed of

*ZacksortB* is a *greeNsort ^{®}* version of

*Zucksort* is a *greeNsort ^{®}* variation of

*ZucksortB* is a *greeNsort ^{®}* version of

The only place

successcomes beforeworkis in the dictionary ― Vince Lombardi

This glossary contains only the most important new and prior-art algorithms implemented in the

*greeNsort*testbed↩︎^{®}‘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↩︎

Copyright © 2020 Dr. Jens Oehlschlägel - All rights reserved - Terms - Privacy - Impressum