For a systematic classification of the algorithms briefly described here1 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 Sedwick 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 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 simpler, faster and as adaptive see ZacksortB.


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.

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

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

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.

Nocosort

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

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

Ninisort is a variant3 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.


Quicksort

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

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.


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). For versions that can sort size-varying elements see VSwansort and XSwansort.


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 WQuicksort24, 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.

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.



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


  1. This glossary contains only the most important new and prior-art algorithms implemented in the greeNsort® testbed↩︎

  2. ‘Inin’ is an acronym for ‘Inplace’ and ‘Into’, the two central functions in Ininsort↩︎

  3. ‘Nini’ sounds like the German ‘Nie nie’ which means ‘never ever’ do more loop checks than needed↩︎

  4. since a stable Quicksort has no ties by definition a WZacksort would be unnecessarily complex and the simpler WQuicksort2 is sufficient↩︎


greeNsort logo


Copyright © 2020 Dr. Jens Oehlschlägel - All rights reserved - TermsPrivacyImpressum