# Chapter 10 Conclusion&Outlook

*greeNsort ^{®}* has rewound sorting research back to 1961 where Toni Hoare invented

*Quicksort*and even further back to 1945 when John von Neumann described

*Mergesort*. From there

*greeNsort*went on a journey through binary sorting in contiguous space.

^{®}*greeNsort*identified and challenged common core-beliefs of the prior art associated with these algorithms, introduced a web of innovations and suggested a classification for them.

^{®}*greeNsort ^{®}* introduced a method for measuring sustainability of algorithms that considers not only

*RUNtime*

*Energy*but also hardware

*%RAM*requirements and combines both into the

*Footprint*measure which allows a fair comparison of algorithms with different memory requirements.

*greeNsort ^{®}* introduced the

*Ordinal-machine*model that motivates robust algorithms which reduce access- and move-distances. Distance-reduction is an under-appreciated feature of

*Quicksort*, and after resolving the

*Quicksort-Dilemma*much of the

*greeNsort*project is about bringing distance-reduction to

^{®}*Mergesort*and other

*Divide&Conquer*algorithms which in the prior art move elements between two distant memory regions.

*greeNsort ^{®}* then introduced

*Symmetric-asymmetry*, an important principle in many sciences, which surprisingly misses in computers science. Sorting and the von-Neumann machine is rife with asymmetries, namely

*Access-asymmetry*,

*Buffer-asymmetry*,

*Order-asymmetry*,

*Pivot-asymmetry*and

*Tie-asymmetry*. Introducing symmetry into problem-solving with these asymmetries results in an enhanced solution space that contains many new methods and algorithms.

Donald Knuth’s mathematical definition of sorting into *Ascending (Asc)* and *Descending (Desc)* addressed *Order-asymmetry* but ignored *Access-asymmetry* which arises as soon as sorting is done in a one-dimensional virtual memory that has *left* to *right* positions. *greeNsort ^{®}* introduces a new definition of

*Symmetric-sorting*which differentiates

*ascending*into

*Ascending from Left (AscLeft)*and

*Ascending from Right (AscRight)*. Using the example of

*Bimesort*it was explained that unstable algorithms can be the consequence of confusing

*right-ascending*with

*left-descending*.

*greeNsort ^{®}* explained that many asymmetric problems can be resolved with

*Symmetric-recursion*, for example the

*Quicksort-Dilemma*– a result of

*Access-asymmetry*and

*Pivot-asymmetry*. Replacing two persistent prior art beliefs by

*No3rd partition*and

*Asymmetric-partitioning*, the solutions were elegant: combining the (symmetric)

*B-level innovation – (F)ast (L)oops (I)n (P)artitioning (FLIP)*and the (lean)

*B-level innovation – (D)istinct (I)dentification for (E)arly (T)ermination (DIET)*methods enabled with the

*Z:cksorts*exactly those symmetric probabilistic algorithms that Tony Hoare tried to design with

*Quicksort1*. Replacing the

*DIET*with the

*B-level innovation – (P)re-(O)rder (E)arly (T)ermination (POET)*method resulted in the even more adaptive

*Ducksort*. This use of symmetry seamlessly led to

*partial sorting*algorithms which consistently handle ties and return more useful information.

*greeNsort ^{®}* explained the space-time trade-off in

*Mergesorts*and the

*Mergesort-dilemma*: that the prior art knows either efficient

*Knuthsort*needing 100% buffer or adaptive but inefficient like

*Timsort*needing 50% buffer.

*greeNsort*explained that unlike

^{®}*Bimesort*,

*Knuthsort*can be made \(\mathcal{O}(N)\) adaptive like

*Timsort*. Introducing

*Data-driven-location*enables

*Omitsort*and combining this with core-belief

*Undirected-sorting*and a new method

*Data-driven-order*enables the bi-adaptive

*Octosort*.

Then with a detour over new methods and algorithms (*Gapped-setup*, *Gapped-merging*, *GKnuthsort*, *Buffer-merging*, *TKnuthsort*, *Crocosort*) *greeNsort ^{®}* arrived at

*Symmetric-merging*which allows distance reducing merging with only 50% buffer or less. Two basic algorithmic methods with different adaptivity were introduced (

*Frogsort*,

*Geckosort*) and several implementation variants explained (

*Frogsort0*and

*Frogsort1*with 50% buffer,

*Frogsort2*with 14% buffer and even much faster than the competition. Alternative to

*Buffer-merging*in the

*Split&Merge*paradigm,

*greeNsort*suggested

^{®}*Buffer-sharing*in the

*Share&Merge*paradigm, which enables

*Frogsort3*with even lower memory requirements (12.5% by default). The Frogsorts 1,2,3 can be joined in doubly parametrized

*Frogsort6*.

*greeNsort ^{®}* then combined

*Symmetric-merging*with the

*Data-driven-order*method of

*Omitsort*to obtain the bi-adaptive

*Squidsort*algorithms, implemented

*Squidsort1*and

*Squidsort2*to show that they provide significant \(\mathcal{O}(N \cdot \log{N})\) adaptivity while – unlike

*Timsort*,

*Peeksort*and

*Powersort*– keeping nocopy-efficiency in hard sorting tasks.

*greeNsort ^{®}* investigated some – possibly new – methods for merge-sorting with \(\sqrt{N}\) buffer or less and found that \(\sqrt{N}\) algorithms (particularly

*Walksort*,

*Jumpsort*) have better

*Footprint*than prior art \(N\log{N}\) algorithms, but not better than the simpler and more general

*Frogsort2*with 14% buffer.

*greeNsort ^{®}* then turned to an under-appreciated generality of

*Mergesorts*: that they can directly sort elements of varying size. Under the

*C-level innovation – (D)irect (S)orting (D)ifferent (S)ize (DSDS)*paradigm, two methods

*B-level innovation – (D)irect (S)orting (N)ull-terminated (S)trings (DSNS)*and

*B-level innovation – (D)irect (S)orting (P)ointered (E)lements (DSPE)*where presented, and the former used to implement

*VKnuthsort*(100% buffer ) and

*VFrogsort1*(50% buffer) which use less

*Energy*(and the latter less memory) than direct sorting methods such as

*UKnuthsort*,

*WQuicksort2*or

*UZacksort*.

*greeNsort ^{®}* completed its exploration of new algorithms by diving into the

*Partition&Pool*paradigm, where – as an exception –

*Wing-partitioning*allows stable binary-partitioning with a single pass over the data per recursion level.

*greeNsort*implemented

^{®}*Kiwisort*(using 100% distant buffer), introduced

*Buffer-partitioning*and particularly

*Symmetric-partitioning*with

*Gapped-wrapup*to obtain

*Swansort*(using 100% local buffer) and finally the travelling

*Storksort*(using 50% local buffer) which can serve an exotic use-case (sorting over a wire).

*greeNsort ^{®}* compared a couple of parallel implementations to substantiate the claim that

*Symmetric-merging*is as general as prior art merging.

*greeNsort*explained its preferred method for lean parallel merging (

^{®}*lean-parallel-merging*) and how to parallelize

*Symmetric-merging*(

*parallel-Symmetric-merging*). After applying them to some of the above algorithms, it was shown that

*PFrogsort0*,

*PFrogsort1*,

*PFrogsort2*and

*PFrogsort3*parallelize almost as well as

*PKnuthsort*.

*greeNsort ^{®}* finally glimpsed on the impact on Incremental sorting, priority-queues and sorted dictionaries. Using the

*greeNsort*classification, the height of the innovations can be quantified: Paradigmatic changes comprise of 12 new core beliefs (C-level innovations) and a new definition of sorting itself (D-level innovation).

^{®}*greeNsort*has introduced 20 new methods (B-level innovations) and 12 further methods (probably known T-level techniques) that allowed to design new algorithms. Here I reported 21 new algorithms, 9 extended algorithms and 8 further algorithms (A-, E- and F-level innovations).

^{®}Finally we looked on the *Impact* of *greeNsort ^{®}* on computational

*Thinking*,

*Research*,

*Teaching*,

*Libraries*,

*APIs*,

*IDEs*,

*Languages*,

*Compilers*and

*Hardware*. Most important: the hand-coded

*Symmetric-recursion*in the test-bed can also be generated with formal

*Code-mirroring*, which leads to

*Symmetric-languages*, mirroring

*Symmetric-compilers*and supporting

*Symmetric-hardware*instructions.

In summary: the aesthetic and ethical compass of the *greeNsort ^{®}* journey lead to

*simplicity*and

*sustainability*, also

*robustness*and

*resilience*. The focus was on

*design*– for low

*distance*. The contribution to research is the

*revision of sorting*and

*bringing symmetry to computer science*. The contribution to teaching is its

*beauty of concepts*and its

*poetry of code*. Welcome to the new era of

*symmetric sustainable sorting*with better trade-offs between generality, simplicity, adaptivity and efficiency. Welcome also to a new field of research: investigating the implications of

*Symmetric-asymmetry*,

*Symmetric-recursion*and

*Code-mirroring*on programming languages, compilers and hardware.