Symmetry

In many disciplines symmetry plays an important role, particularly bi-symmetry. Examples are vertebrates in biology, vehicles in engineering and churches in architecture. By contrast, in writing program code symmetry seems to play no relevant role! 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
• 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)

as is the topic of sorting

• Order-asymmetry the fact that that ‘order’ is asymmetric and reaches from ‘low’ to ‘high’ ‘keys’
• 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
• 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)

Bi-Symmetry as a design principle is rare, and if, bi-symmetry is mostly used on a loop-level. The secret ingredient of the new greeNsort^® algorithms is the symmetric-asymmetry principle often found in nature, engineering and arts: design low-level asymmetry and turn it into high-level symmetry by mirroring. For algorithmic-code this means: do not fight but embrace loop-level asymmetries and create recursion-level symmetry. Instead of the usual divide&conquer self-recursive functions, greeNsort^® uses mutual-recursive code-mirrored functions. Code-mirroring enhances the algorithmic solution space, which contains many unexplored areas and surprising solutions. This begins with a new definition of ‘sorting’: