# Chapter 2 Paradigmatic innovations

## 2.1 Ordinal-machine model

`innovation("Ordinal-machine","C*","minimize monotonic cost of distance")`

The prior art uses specific machine models, like the *random-access-model* or the *IO-model* with specific assumptions on the costs for accessing and moving data. Those machine models are the basis for analyzing algorithms and proving certain properties. This precise mathematical approach suggests that those machine models represent real machines, which is rarely the case. Furthermore this approach focuses academic efforts on analysis and proof rather than on development of better algorithms. Algorithms and even software have a longer lifetime than particular machines, therefore they should be *robust* against variations in technology and *resilient* in environment with little hardware resources. The algorithm developer cannot know on which machines his code will run, more and more he cannot even know the details of current machines, because they are more and more virtualized in the cloud. Hence *greeNsort*^{®} follows a different approach. A non-specific *Ordinal-machine* model simply assumes that the *cost of access and moves* is a *monotonic function of distance* in a memory address space that reaches from *left* to *right*. For a constant distance cost in the classic random-access-model there is a constant \(\mathcal{O}(1)\) cost per move, linear \(\mathcal{O}(N)\) cost per level and \(\mathcal{O}(N\log{N})\) for the total cost of *Divide&Conquer* sorting. Now consider the popular *AlgoRythmics* videos which teach sorting by folk-dances: the movement cost of the dancers on stage is a linear function of distance, hence the cost of the same sorting algorithm is suddenly \(\mathcal{O}(N)\) per move, quadratic \(\mathcal{O}(N^2)\) cost per level and \(\mathcal{O}(N^2\log{N})\) for the total cost of *Divide&Conquer* sorting. Today’s computers have distance costs in between, say \(\mathcal{O}(\log{N})\) per move, \(\mathcal{O}(N\log{N})\) per level and \(\mathcal{O}(N\log{N}^2)\) for the total cost of *Divide&Conquer* sorting.

From a practical point of view, assuming a *Ordinal-machine* focuses on quick iteration of developing new algorithms, experimenting with them and improving them, rather than proving mathematical properties based on pseudo-exact machine-assumptions. For *greeNsort*^{®} this implies a focus on *distance minimization* and *sustainable measurement*.

## 2.2 Sustainable measurement

`innovation("Footprint","C*","measure variableCost x %fixedCost")`

The prior art empirically evaluates algorithms by measuring *RUNtime*, *CPUtime* or by counting certain operations such as, comparisons, moves, swaps, cache-misses etc. This addresses the CO2 variable cost of running the software but ignores the CO2 fixed cost embodied in producing the hardware^{4}. *greeNsort*^{®} introduces the *Footprint*, which multiplies variable cost with relative fixed-cost (per element, not absolute). *greeNsort*^{®} uses:

as a proxy and*(R)andom (A)ccess (M)emory (RAM)*as a normalized proxy for fixed cost hardware requirements,*%RAM*(RAPL), or simpler*Energy*or*CPUtime*as proxies for variable costs of running the software*RUNtime*,*tFootprint*and*cFootprint*as single-scale measures of variable costs penalized for fixed costs (*eFootprint**runTime*,*CPUtime*and*Energy*multiplied with*%RAM*)

*Footprints* allow to compare algorithms with different memory-speed trade-offs. Optimizing for Footprints avoids the pitfalls of extreme choices: just minimizing *CPUtime* or *Energy* can lead to excessive memory (and hardware) consumption; attempting in-place sorting with zero-buffer-memory has been of great academic interest but never lead to practically convincing algorithms. This new paradigmatic choice of measuring algorithms has enabled *greeNsort*^{®} algorithms with better memory-speed trade-offs aka better trade-offs between execution CO2 of electricity and embodied CO2 of hardware. For details on measuring RAPL-energy and *eFootprints* see the *Methods&Measurement* section.

## 2.3 Symmetry principle

`innovation("Symmetric-asymmetry","C*","low-level-asymmetry, high-level-symmetry")`

### 2.3.1 Symmetry

In biology, engineering and architecture *symmetry* plays an important role, particularly *bi-symmetry*. But strangely not in Computer Science! Yes, there are publications on *symmetry detection* algorithms, but there symmetry is only the object, not the subject of the design: Symmetry is rarely considered a major design principle for algorithms and code. Although a one-dimensional left-right-memory-address-space should be an invitation for bi-symmetry.

A notable exception is *Quicksort1*, which was designed symmetrically by Hoare (1961b), Hoare (1961a): two pointers move from left and right until they meet an element that is on the wrong side. Unfortunately the search *cannot* be symmetric in a von-Neumann-Machine: first one pointer searches, then the other, this can create heavy imbalance, hence can lead to \(\mathcal{O}(N)\) recursion depth and \(\mathcal{O}(N^2)\) execution cost for certain inputs. The popular *Quicksort2* which goes back to Singleton (1969) stops pointers on pivot-ties: this guarantees a balanced partition but at a costly price: pivot-ties are swapped with no benefit and worse the partitioning is not *MECE* and does not early-terminate on ties.

Symmetric pointer search can be approximated by alternating between moving the left and right pointer. The *greeNsort*^{®} algorithm *Chicksort* implements this, and it indeed avoids swapping pivot-ties, but it is *slower* than *Quicksort2* due to the more complex loop structure. I did not explore block-wise alternating pointer search, because there is a much better solution (see the *The Quicksort-Dilemma*).

In biology, engineering and architecture *symmetry* is often composed high-level from low-level asymmetries. *greeNsort*^{®} is built on transferring the *Symmetric-asymmetry* concept to computer science: C-level innovation – embracing low-level-asymmetry within high-level-symmetry, see *Symmetry principle*

### 2.3.2 Asymmetries

The von-Neumann-Machine is rife with asymmetries

*Access-asymmetry*the fact that memory access is asymmetric either the left element first then the right one or the right element first and then the left one, see*Asymmetries**Buffer-asymmetry*the fact that buffer placement relative to data is asymmetric, data may either be placed left of buffer memory (DB) or right of buffer memory (BD), see*Asymmetries*

as is the topic of sorting

*Order-asymmetry*the fact that that ‘order’ is asymmetric and reaches from ‘low’ to ‘high’ ‘keys’, see*Asymmetries**Pivot-asymmetry*the fact that a binary pivot-comparison (one of*[LT]*,*[LE]*,*[GT]*,*[GE]*) assigns an element equal to the pivot either to one partition or the other, see*Asymmetries**Tie-asymmetry*the fact that stable ties are asymmetric, they may represent their original order either from left to right (LR) or from right to left (RL), see*Asymmetries*

How does one embrace low-level-asymmetry within high-level-symmetry? Let’s start with a new definition of sorting.

## 2.4 Definition of sorting

`innovation("Symmetric-sorting","D","'ascleft', 'ascright', 'descleft', 'descright'")`

According to Knuth D. E. Knuth (1998), p. 1 sorting is *“the rearrangement of items into ascending or descending order”* and can be distinguished into *stable* and *unstable* sorting. This definition creates four different goals for sorting “*unstable ascending*”, “*unstable descending*”, “*stable ascending*”, and “*stable descending*”. Sorting libraries implement all four or a subset of these four. From Knuth’s mathematical perspective the definition of sorting is perfect.

However, in the context of computers, algorithms are not abstract, they operate on *elements* that are stored in *memory* that is addressed from left to to right address *locations* (address locations are notated here from left to right in order to not confuse this with low and high sorting keys). Habitually ascending and descending sequences are written from *left* to *right* :

The two abstract sorting sequences *Ascending (Asc)* and *Descending (Desc)* correspond to four concrete sorting sequences in memory: *Ascending from Left (AscLeft)*, *Ascending from Right (AscRight)*, and *Descending from Left (DescLeft)*, and *DescLeft*. The Difference between *DescLeft* and *AscLeft*, is a reverted - but stable - sequence of ties!

A first example for the immediate benefits of the *greeNsort*^{®} definition is found in section *Reference algo (Knuthsort)*. The *greeNsort*^{®} definition is powerful because it facilitates reasoning and increases the size of the solution space, like the invention of the *imaginary part* increased the number space from *real numbers* to *complex numbers*, such that suddenly the square-root of a negative number was defined.

## 2.5 Recursion model

```
innovation("Mutual-recursion","T*","is more expressive than self-recursion")
innovation("Symmetric-recursion","C*","symmetric mutual recursion")
dependency("Symmetric-recursion", "Mutual-recursion")
dependency("Symmetric-recursion", "Symmetric-asymmetry")
dependency("Symmetric-recursion", "Code-mirroring")
```

Some people consider *recursion* to be a technical topic, and *tail-recursion* indeed is. However, recursion is first and foremost a mental tool, that helps humans to organize code and understand algorithms. Proof? Because each recursion can be written as loops. QED.

In the context of sorting algorithms prior art recursion usually means *self-recursion*. However, there are good reasons – explained in the book – to assume that *Mutual-recursion* is a more natural and powerful mental problem-solving device than self-recursion. Even without this assumption: mutual recursion is definitely *more expressive* than self-recursion. Mutual-recursion is not new^{5}, but undervalued. Why? Because mutual-recursion is a natural fit for binary *Divide&Conquer* algorithms.

*Divide&Conquer* in sorting means dividing and conquering *address ranges*, i.e. ranges from *left* to *right*. *greeNsort*^{®} is built on *Symmetric-recursion*, a new class of mutual-recursions where two functions co-operate recursively in a more or less symmetric fashion, and where the symmetry axis is left-right memory, not ascending-descending order.

And here is the final answer to the question how to embrace low-level-asymmetry within high-level-symmetry: instead of the failing prior art approaches to achieve symmetry in loops, *greeNsort*^{®} embraces asymmetry in loops and creates a higher-level symmetry in mutual-recursion. You will soon see this at work.

## 2.6 Mirroring code

```
innovation("Code-mirroring","C*","left-right mirroring of code")
innovation("Symmetric-language","C*","symmetric programming language")
dependency("Symmetric-language", "Code-mirroring")
innovation("Symmetric-compiler","C*","compiling symmetric language")
dependency("Symmetric-compiler", "Symmetric-language")
innovation("Symmetric-hardware","C*","instructions for mirroring code")
dependency("Symmetric-hardware", "Symmetric-compiler")
```

The *Wikipedia entry for binary search* contains one of the few references to symmetric behavior: searching for the leftmost or rightmost element in case of ties. However, that the two functions given behave symmetrically is not easy to see, because the code is not symmetric. Achieving symmetry by mirroring the code itself has advantages: it is easier to verify correct and code-mirroring can be done formally and automatically.

As a research project, the *greeNsort*^{®} algorithms have been developed and written largely manually. But the symmetric properties of the two functions calling mutually in *Symmetric-recursion* are an invitation to create one of them by mirroring code sections of the other, either with meta-programming techniques or with new language constructs that support *Code-mirroring*, see the demonstration of the feasibility of Code-mirroring in a (interpreted) R-implementation of *Zacksort* in the *Languages* section. If code-mirroring is supported by languages, compilers and hardware, then the cost of code-duplication in *Symmetric-recursion* can be avoided. The opportunity is: writing elegant parsimonious code once, mirror-it with language constructs and the compiler translates this into hardware-instructions for mirroring sections of instructions. This is a promising new field of research.

## 2.7 Further techniques

```
innovation("Divide&Conquer","T*","Recursive divide and conquer paradigm")
innovation("COMREC","T*","COMputing on the RECursion")
innovation("NORELORE","T*","NO-REgret LOop-REuse")
innovation("DONOTUBE","T*","DO NOt TUne the BEst-case")
dependency("Mutual-recursion","COMREC")
```

In the broadest sense, mutual recursion is a special case of a broader technique: *T-level technique - (COM)puting on the (REC)ursion (COMREC)*. *COMREC* is a simple powerful technique, not as complicated and expressive as meta-programming. *Meta-programming* tends to be not only expressive but also inefficient, particularly *programming on the language* in interpreted languages such as *R* or *Python*^{6}. *COMREC* can be easily compiled to efficient executable code. Beyond *Symmetric-recursion*, further examples of this technique are nested recursive functions, where different functions are used for different problem sizes. The most popular use-case is tuning with *Insertionsort* for problem sizes smaller than a cut-off, the *greeNsort*^{®} algorithms use an `INSERTIONSORT_LIMIT`

of 64.

Equal tuning is an example of another *greeNsort*^{®} principle: equal implementation quality for fair comparison. An exception is *Timsort*, which violates the simplicity-principle and hence the test-bed uses an existing implementation, see 2nd Reference (Timsort).

Finally, three principles should be mentioned, that are immediately applied in the section on *Quicksort algorithms*:

**Robustness**:*greeNsort*^{®}Partition&Pool algorithms are using*random pivots*which guarantees a \(\mathcal{O}(N\log{N})\) average case for*any*data input. Using deterministic pivots cannot guarantee an \(\mathcal{O}(N\log{N})\) average case, the analyses of Sedgewick (1977b) which claim this are based on the nonsense-assumption that instead the input data be random, this is irresponsible for production use (unless recursion-depth is guarded and limited as in*Introsort*).:*NORELORE**greeNsort*^{®}algorithms use optimizations that avoid extra-operations and memory scanning by reusing and melting loops for different purposes.:*DONOTUBE**greeNsort*^{®}algorithms may invest extra-operations to enable best-case behavior but do not invest extra-operations to speed-up best-cases.

The

*Green Software Foundation*has recently (2021) suggested the Software Carbon Intensity (SCI), which attempts an end-to-end measurement of variable costs and fixed costs on a common CO2-scale. This, however, is not pragmatic: it considers factors that are not attributes of software and that are not available to software developers (energy/instruction of hardware, CO2/energy of location). Furthermore the SCI has the paradoxical feature that in locations with 100% renewable energy the electricity is assumed to have zero costs such that purely the hardware amortization determines the SCI. For more details see my*comment to the SCI*and my*presentation at the GSF*↩︎In sorting it is rare, I am aware only of Sedgewick’s “superoptimization” which combines

*nocopy-Mergesort*with a*bitonic merge strategy*, see*First algo (Bimesort)*↩︎for the inefficiency of Python see

*Enhancing the Software Carbon Intensity (SCI) specification of the Green Software Foundation (GSF)*↩︎