Definition of sorting

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.

Figure 1: Knuth’s definition of sorting

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 :

Figure 2: Conventional interpretation: from left to right

The two abstract sorting sequences asc and desc correspond to four concrete sorting sequences in memory: ascleft, ascright, and descleft, and descleft. The Difference between descleft and ascleft, is a reverted - but stable - sequence of ties!

Figure 3: greeNsort definition: unstable sorting has two API targets (AscPoor, DescPoor) but stable symmetric sorting has four API targets (AscLeft, AscRight, DescLeft and DescRight)

The greeNsort^® definition is powerful because it facilitates reasoning in an increased solution space; there is similarity to the invention of the imaginary part which increased the number space from real numbers to complex numbers, such that suddenly the square-root of a negative number was defined.