# Chapter 9 Impact

In this section we give a perspective on the impact of the *greeNsort*^{®} innovations on computational *Thinking*, *Research*, *Teaching*, *Libraries*, *APIs*, *IDEs*, *Languages*, *Compilers* and *Hardware* – to the degree that we already can imagine them today.

## 9.1 Thinking

I expect that the surprisingly successful development of the *greeNsort*^{®} methods and algorithms with very few man years investment could somewhat change today’s *computational thinking*. Liu et al. (2021) have already questioned the current scope as too narrow, I agree, but I think that their approach which adds *historical-thinking*, *data-centric-thinking* and *architectural thinking* still jumps too short. I plan a book chapter that will take a look at *recursive-thinking*, *symmetric-thinking*, *aesthetical-thinking*, *ethical-thinking* and *experimental-thinking* and their role in *problem-solving* for a *sustainable-society*.

## 9.2 Research

I expect short-term, mid-term and long-term impact on research:

- short-term: research on existing
*greeNsort*^{®}*algorithms*(like the publications following of the publication of*Dual-Pivot-Quicksort*of @Yaroslavskiy (2009), namely Wild (2012), Wild and Nebel (2012), Wild et al. (2013), Wild, Nebel, and Neininger (2015), Aumüller and Dietzfelbinger (2015), Martínez, Nebel, and Wild (2015), Aumüller, Dietzfelbinger, and Klaue (2016), Nebel, Wild, and Martínez (2016), Wild, Nebel, and Mahmoud (2016), Wild (2016), Wild (2017), Wild (2018a), Wild (2018b), Martínez, Nebel, and Wild (2019)) - mid-term: research applying
*greeNsort*^{®}*methods*and*principles*to further algorithmic problems - long-term: research on
*programming languages*,*compilers*and*CPUs*that support*greeNsort*^{®}methods, particularly*Code-mirroring*

For example, the *B-level innovation – (D)istinct (I)dentification for (E)arly (T)ermination (DIET)* and *B-level innovation – (F)ast (L)oops (I)n (P)artitioning (FLIP)* methods have first been proven useful for solving *Quicksort-Dilemma* in *unstable binary* sorting, and then gave way to *Ducksort*. The section *Partial Z:cksort* has shown further implications for various closely related partial sorting algorithms, and section *Incremental sorting* has shown further implications for not so closely related priority queues. So far unstable sorting. Then DIET and FLIP could also be applied to *stable* binary *Partition&Pool* sorting, and I suspect it could play a role in *k-ary* *Partition&Pool* sorting, at least help to make *(I)n-place (P)arallel (S)uper (S)calar (S)ample(So)rt (IPS4o)* stable. From a more abstract perspective, the broadest implication of the *symmetric thinking* and *recursive thinking* behind *DIET* and *FLIP* is that they open the door to a new, unexplored part of an enlarged solution space for many algorithmic problems. In the statistical programming languages S and R there is the concept of *“computing on the language”*; this means using code to create code which is then executed; this increases the expressiveness of these interpreted languages but comes as a performance penalty. The *FLIP* method is an example of *computing on the recursion* which also increases expressiveness, but without such performance penalties. Clearly, if for each recursive recall we have to choose between *two* mirrored versions of code, this increases expressiveness by factor 2. In other words: *computing symmetry on the recursion* increases the solution space for algorithmic problems by at least factor 2. If we consider, that we actually do not mirror *all* code but *selected* code sections, the number of possible variations is higher than 2 (of which many are not useful, but some might). Of course, since all recursive algorithms can be coded without recursion, all of this enlarged solution space can theoretically be reached without *computing symmetry on the recursion*, but in practice, algorithms need to be written by humans who understand what they do, and hence *recursion* and *symmetry* are helpful *mental tools* for understanding problems and designing algorithms. Hence the concept of *computing symmetry on the recursion* is a powerful mental instrument that combines *recursive thinking*, *symmetric thinking* and *spatial thinking*. *Code mirroring* is at the junction between verbal and visual cognitive abilities, and that plays a role in problem solving and innovating. In summary, *computing symmetry on the recursion* is promising

- because of its potential to simplify (and visualize) complex algorithmic tasks
- because it is widely unexplored terrain
- because the inherent redundancy provides further optimization opportunities, see [
*Languages*]

Note that this outlook has not even touched on the major share of the *greeNsort*^{®} innovations: *Split&Merge* sorting. It also has not touched on *index-trees*. The following quote shows a common belief that symmetric tree-traversal is not interesting:

Binary tree is a tree structure, traversal is to make all nodes in the tree be visited only once, that is, arranged into a linear queue according to certain rules. A binary (sub) tree is a recursively defined structure, consisting of three parts: the root node (N), the left subtree (L), and the right subtree (R). Classify the traversal of the binary tree according to the access order of these three parts. There are 6 traversal schemes in total: NLR, LNR, LRN, NRL, RNL and LNR. Studying the traversal of binary trees is to study these 6 specific traversal schemes. Obviously, according to simple symmetry, the traversal of the left and right subtrees can be interchanged, that is, NLR and NRL, LNR and RNL, LRN and RLN Therefore, it is only necessary to study the three types of NLR, LNR and LRN, which are called “pre-order traversal”, “medium-order traversal” and “post-order traversal”.

— TitanWolf - Binary tree traversal

Assuming upfront that mirrored versions of tree-operations can be ignored looks again like unexplored opportunities of a larger solution space.

## 9.3 Teaching

I expect short-term, mid-term and long-term impact on teaching:

- short-term: teaching existing
*greeNsort*^{®}*algorithms*,*methods*and*principles*. It is obvious, that textbooks on algorithms require updating their sections on*unstable sorting*,*partial sorting*and*selection*and*priority queues*. The same is true for sections on*stable sorting*and*incremental sorting*. Beyond that, textbooks need to update theirs sections on*recursion*and should teach the*greeNsort*^{®}methods (such as*code-mirroring*and*computing-on-the-recursion*) and principles (such as*measuring sustainability*and*designing for simplicity*). - mid-term: teaching the algorithms that result from research using
*greeNsort*^{®}methods and principles, see above - long-term: teaching the results of research on
*programming languages*,*compilers*and*CPUs*that support*greeNsort*^{®}methods, see above and below

## 9.4 Libraries

The first motivation for *greeNsort*^{®} was to provide more efficient sorting libraries in order to reduce CO2-emissions. Because of the bigger savings potential of *stable sorting* the focus of *greeNsort*^{®} is on alternatives to *Mergesort*, that save both, electricity and memory. Nonetheless, unstable *Quicksort* plays an important role in IT and most programming languages have an API for unstable in-place sorting, often using implementations inferior to *Pdqsort*, *Z:cksort* or *Ducksort*. *Z:cksorts* allow simple and efficient implementation which is superior to both *Quicksort2* and *Quicksort3*, notwithstanding further tuning. For example the C `sort`

routine implements *3-way-Quicksort*. *Z:cksort* can replace it with the benefit of faster sorting untied data and still early terminating in tied data. The simplicity of *Z:cksort* facilitates verification of correctness of implementations.

Much more impact on sorting libraries is to be expected from the *greeNsort*^{®} Split&Merge algorithms with their superior trade-off between memory and speed.

## 9.5 APIs

Each *Z:cksort* uses two binary comparison operators: `EQ`

in the DIET loop and then `GT`

(or `LT`

) and `LE`

(or `GE`

). All of them can be derived from the `{-1|0|+1}`

output of the ternary `cmd`

-function which the C `sort`

API takes as a parameter. However, using `cmp`

is not efficient, because internally it always requires *two* comparisons, whatever the usage of its output is. Hence, further efficiency gains should be possible by creating a new API taking three binary comparison operators, or at least two of them. For those to whom this sounds overkill: C++ has introduced syntax for exactly this. I plan a book chapter on optimal design for sorting APIs.

## 9.6 IDEs

If *symmetric thinking* indeed gains importance in algorithm design, programmers will push for IDE support for mirroring code, for example ‘copy’ and ‘paste mirrored’. However, that does not remove the burden to maintain the mirrored code, furthermore not all language element allow for mirroring, therefore more fundamental support for symmetry will be needed in *Languages*, *Compilers* and *Hardware*.

## 9.7 Languages

The mirroring of code in the *FLIP*-method comes with programming effort. Mirroring a piece of code is less work and less error-prone compared to writing new code, but still writing and maintaining it is work. However, it is work that can be automated by an interpreter, by a pre-processor or by a compiler. In other words: it is to be expected, that the *FLIP* method will have impact on future design of meta-programming or programming languages in order to facilitate programmer effort and minimize programming errors. To demonstrate this, we give an implementation of *Zacksort* in *R*^{25}. *R* is an advancement of the *S* language. It is related to scheme, a LISP dialect, and as such treats code as data and allows “computing on the language”, in other words: meta-programming is built into the language. Note that this is just a demonstration of feasibility, since R as an interpreted language it too slow to be a serious implementation language for sorting algorithms. Having said this, let’s do it. First we need the usual comparison functions:

```
<- function(a,b)a==b
EQ <- function(a,b)a<=b
LE <- function(a,b)a>b
GT <- function(a,b)a<b
LT <- function(a,b)a>=b GE
```

The `SELF`

-function returns the code (parse tree) of the current function, and the `KEEP`

-function protects code from being mirrored (and executes the code):

```
<- function(){
SELF sys.function(sys.parent())
}
```

```
<- function(exp){
KEEP eval.parent(substitute(exp))
}
```

The following `FLIP`

-function returns a mirrored function of `f`

(assuming `f`

conforms with certain rules encoded in `FLIP`

):

```
<- function (f)
FLIP
{<- function(e) {
flip if (is.call(e)) {
if (is.symbol(e[[1]])) {
if (e[[1]] != as.symbol("KEEP")) {
for (i in seq_along(e)) {
<- flip(e[[i]])
e[[i]]
}
}
e
}else {
e
}
}else if (is.symbol(e)) {
<- as.character(e)
s if (length(grep("_tieleft$",s))==1){
<- sub("_tieleft","_tieright",s)
fs else if (length(grep("_tieright$",s))==1){
}<- sub("_tieright","_tieleft",s)
fs else{
}<- switch(s
fs l = "r" , r = "l"
, i = "j" , j = "i"
, f = "g" , g = "f"
, `+` = "-" , `-` = "+"
, `<` = ">" , `>` = "<"
, `<=` = ">=", `>=` = "<="
, LT = "GT" , GT = "LT"
, LE = "GE" , GE = "LE"
,
, s
)
}as.symbol(fs)
}else {
e
}
}<- f
g body(g) <- flip(body(g))
return(g)
}
```

Here is a version of *Zocksort* simply calling itself via `SELF()`

instead of the R-typical `Recall`

-function:

```
<- function(x, l=1, r=length(x))
zocksort
{if (l >= r)
return<- sample(r-l+1, 1)
j <- x[j]
v c(l,j)] <- x[c(j,l)] # SWAP pivot
x[# DIET LOOP
<- l
i while (EQ(x[i <- i+1], v))
if (i >= r)
return(x) # early termination
# MAIN LOOP
<-i-1; j<-r+1
irepeat{
while ({j <- j-1; GT(x[j], v)}) # sentinel stop
NULL}
{while ({i <- i+1; LE(x[i], v)})
if (i >= j) # explicit stop
break
if (i >= j)
break
c(i,j)] <- x[c(j,i)] # SWAP
x[
}c(l,j)] <- x[c(j,l)] # SWAP pivot back
x[<- j
m <- SELF() # h(...) replaces Recall(...)
h <- m - l; if (n>1) x[l:(m-1)] <- h(x[l:(m-1)], 1, n)
n <- r - m; if (n>1) x[(m+1):r] <- h(x[(m+1):r], 1, n)
n return(x)
}
```

This is *Zacksort* calling a flipped version of itself:

```
<- function(x, l=1, r=length(x))
zacksort
{KEEP(
if (l >= r)
return
)<- KEEP(sample(r-l+1, 1))
j <- x[j]
v c(l,j)] <- x[c(j,l)] # SWAP pivot
x[# DIET LOOP
<- l
i while (EQ(x[i <- i+1], v))
if (i >= r)
return(x) # early termination
# MAIN LOOP
<-i-1; j<-r+1
irepeat{
while ({j <- j-1; GT(x[j], v)}) # sentinel stop
NULL}
{while ({i <- i+1; LE(x[i], v)})
if (i >= j) # explicit stop
break
if (i >= j)
break
c(i,j)] <- x[c(j,i)] # SWAP
x[
}c(l,j)] <- x[c(j,l)] # SWAP pivot back
x[<- j
m <- FLIP(SELF())
h KEEP({
<- m - l; if (n>1) x[l:(m-1)] <- h(x[l:(m-1)], 1, n)
n <- r - m; if (n>1) x[(m+1):r] <- h(x[(m+1):r], 1, n)
n
})return(x)
}
```

This is the *flipped* *Zacksort*:

```
> FLIP(zacksort)
function (x, l = 1, r = length(x))
{KEEP(if (l >= r)
return)<- KEEP(sample(r - l + 1, 1))
i <- x[i]
v c(r, i)] <- x[c(i, r)]
x[<- r
j while (EQ(x[j <- j - 1], v)) if (j <= l)
return(x)
<- j + 1
j <- l - 1
i repeat {
while ({
<- i + 1
i LT(x[i], v)
}) {
}while ({
<- j - 1
j GE(x[j], v)
if (j <= i)
}) break
if (j <= i)
break
c(j, i)] <- x[c(i, j)]
x[
}c(r, i)] <- x[c(i, r)]
x[<- i
m <- FLIP(SELF())
h KEEP({
<- m - l
n if (n > 1)
:(m - 1)] <- h(x[l:(m - 1)], 1, n)
x[l<- r - m
n if (n > 1)
+ 1):r] <- h(x[(m + 1):r], 1, n)
x[(m
})return(x)
}
```

For comparison the double-flipped *Zacksort* (standardized without code comments):

```
> FLIP(FLIP(zacksort))
function (x, l = 1, r = length(x))
{KEEP(if (l >= r)
return)<- KEEP(sample(r - l + 1, 1))
j <- x[j]
v c(l, j)] <- x[c(j, l)]
x[<- l
i while (EQ(x[i <- i + 1], v)) if (i >= r)
return(x)
<- i - 1
i <- r + 1
j repeat {
while ({
<- j - 1
j GT(x[j], v)
}) {
}while ({
<- i + 1
i LE(x[i], v)
if (i >= j)
}) break
if (i >= j)
break
c(i, j)] <- x[c(j, i)]
x[
}c(l, j)] <- x[c(j, l)]
x[<- j
m <- FLIP(SELF())
h KEEP({
<- m - l
n if (n > 1)
:(m - 1)] <- h(x[l:(m - 1)], 1, n)
x[l<- r - m
n if (n > 1)
+ 1):r] <- h(x[(m + 1):r], 1, n)
x[(m
})return(x)
}
```

and finally *Zucksort* which calls itself on the non-critical branch but its flipped-self on the critical branch:

```
<- function(x, l=1, r=length(x))
zucksort
{KEEP(
if (l >= r)
return
)<- KEEP(sample(r-l+1, 1))
j <- x[j]
v c(l,j)] <- x[c(j,l)] # SWAP pivot
x[# DIET LOOP
<- l
i while (EQ(x[i <- i+1], v))
if (i >= r)
return(x) # early termination
# MAIN LOOP
<-i-1; j<-r+1
irepeat{
while ({j <- j-1; GT(x[j], v)}) # sentinel stop
NULL}
{while ({i <- i+1; LE(x[i], v)})
if (i >= j) # explicit stop
break
if (i >= j) break
c(i,j)] <- x[c(j,i)] # SWAP
x[
}c(l,j)] <- x[c(j,l)] # SWAP pivot back
x[<- j
m <- SELF()
g <- FLIP(g)
f KEEP({
<- m - l; if (n>1) x[l:(m-1)] <- f(x[l:(m-1)], 1, n)
n <- r - m; if (n>1) x[(m+1):r] <- g(x[(m+1):r], 1, n)
n
})return(x)
}
```

We can formally verify the code-symmetry as true:

```
> # standardize Zacksort and Zucksort
> zacksort <- FLIP(FLIP(zacksort))
> zucksort <- FLIP(FLIP(zucksort))
> # single flip modifies the functions
> all.equal(FLIP(zacksort), zacksort)
1] "target, current do not match when deparsed"
[> all.equal(FLIP(zucksort), zucksort)
1] "target, current do not match when deparsed"
[> # double flip is idempotent
> all.equal(FLIP(FLIP(zacksort)), zacksort)
1] TRUE
[> all.equal(FLIP(FLIP(zucksort)), zucksort)
1] TRUE [
```

This section has shown that algorithms using the *FLIP*-method can be written without mirror-duplicating code-redundancy, in suitable languages.

## 9.8 Compilers

The above interpreted `FLIP`

operation at runtime in each call of the R-zacksort is very inefficient. It is better to only do this only once at compile time. The seemingly least invasive thing to do is using meta-programming – for example the C-preprocessor – for creating mirrored versions of code, which then is compiled along the standard path, without any particular support for symmetry in the language, the compiler or the hardware. However, there might be reasons to consider symmetry in the language itself. For example many languages provide ‘iterators’; these usually have a standard iteration direction and might not support efficient iteration in the reverse direction. C++, C# and Java have bi-directional iterators, Python and Rust have not, Mapcar in Lisp is unidirectional.

## 9.9 Hardware

Supporting symmetry in compilers but not in hardware still comes at a price: binary code duplication uses space in the instruction cache. If symmetric programming finds widespread use, then hardware support for symmetry – for example a FLIP instruction – might provide benefits. Co-design of language, compilers and hardware for symmetric programming is an interesting topic for future research.

## 9.10 Impact conclusion

Without knowing what will happen, I see good reasons to believe that – beyond saving time, energy and hardware – the *greeNsort*^{®} innovations can have substantial impact on computational *Thinking*, *Research*, *Teaching*, *Libraries*, *APIs*, *IDEs*, *Languages*, *Compilers* and – hopefully – *Hardware*.