- Bimesort
- Copysort
- Dupisort
- Ducksort
- DucksortB
- Frogsort
- Frogsort0
- Frogsort1
- Frogsort2
- Frogsort3
- Geckosort
- Grailsort
- Heapsort
- Ininsort
- Introsort
- IS4o
- IPS4o
- Jumpsort
- Katasort
- Katasort3
- Katasort4
- Knuthsort
- Knuthsort3
- Knuthsort4
- Mergesort
- MFrogsort2
- MKnuthsort
- NFrogsort2
- NKnuthsort
- Nocosort
- Natural-Mergesort
- Ninisort
- Omitsort
- Octosort
- Pdqsort
- Peeksort
- Powersort
- PDucksort
- PDucksortB
- PFrogsort0
- PFrogsort1
- PFrogsort2
- PFrogsort3
- PKnuthsort
- Quicksort
- Quicksort1
- Quicksort2
- Quicksort2B
- Quicksort3
- Quickpartial
- Quickselect
- Skasort
- Sqrtsort
- Squidsort
- Squidsort1
- Squidsort2
- Swansort
- Timsort
- Tricksort
- Walksort
- UZacksort
- XFrogsort1
- XSwansort
- VFrogsort1
- VSwansort
- WQuicksort2
- Zacksort
- ZacksortB
- Zucksort
- ZucksortB
- Zackpartial
- Zackselect
- Zuckpartial
- Zuckselect

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

*Ducksort* is a *greeNsort ^{®}* algorithm that
enhances

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

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

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

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

*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*^{3} 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
needing negligible buffer

*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^{4} 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*.

*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* 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* 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* 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* 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* 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* 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* is a variant^{5} 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.

*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* 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* is a branch-parallel version of *Ducksort*, see also *PQuicksort2* and *PKnuthsort*.

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

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

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

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

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

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

*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

*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

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

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

successcomes beforeworkis 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):**F**lip**R**ecursive**O**rganized**G**aps↩︎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↩︎

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