greeNsort® open-sourced Symmetric Sustainable Sorting algorithms that save energy and/or hardware

The beauty feature of mirror symmetry can be found in biology, engineering, architecture, art and mathematics, but not as a design principle in programming languages and algorithms. While doing research on energy-efficient algorithms, German database architect Jens Oehlschlägel discovered that symmetry can be used to make multiple widespread divide-and-conquer algorithms more efficient, robust and resilient.

60 years after Tony Hoare’s Quicksort, Zacksort is the algorithm that Hoare envisioned: a symmetric probabilistic algorithm that is efficient like binary Quicksort but early terminates on ties like ternary Quicksort.

75 years after John von Neumanns Mergesort, Frogsort is an algorithm that merges not only data but also buffer. Frogsort has cache-locality close to Quicksort, needs only 50% buffer (or less) and is adaptive without tuning.

The greeNsort^® algorithms use symmetric mutual-recursion, a symmetric sorting definition and a footprint measure which allows a sustainability-ranking of algorithms with different RAM and CPU trade-offs. Oehlschlägel believes that “symmetry changes how binary sorting will be taught and used” and he invites all professionals to update their teaching materials and sorting libraries “because global warming requires action to reduce the footprint of IT”.

https://greensort.org provides more information and https://github.com/greeNsort provides an R-package with 150 algorithms written in C and an R-testbed with data-generators and introductory vignettes for quickstart, measurement and development.

Munich, February 7, 2024