Conclusion

greeNsort^® presents a new perspective on binary divide&conquer sorting: Simple Symmetric Sustainable Sorting deliberately departs from the state of the art and previous habits, enabling new algorithms. Our Footprint KPIs combine traditional operational costs (time, energy) with hardware investment requirements (memory) and enable ranking of algorithms with different memory requirements. Our symmetric definition of sorting (four stable API targets instead of two) clarifies how to write robust algorithms. Our ordinal machine model promotes the development of robust algorithms by focusing on minimizing distances. New algorithms are enabled in an enlarged solution-space by embracing asymmetry (of partitioning and of loops in von-Neumann machines) and delegating symmetry into (mutual) recursion design. Our main results are are new Quicksort which solves the Quicksort-Dilemma and a new Mergesort which resolves the Mergesort-Trilemma (and novel variations of those algorithms).

60 years after Hoare’s Quicksort, we present the algorithm that Hoare wanted to invent: a symmetric probabilistic algorithm that early terminates on ties without compromising efficiency. Zacksort resp. Zucksort combine the symmetric FLIP method with the lean DIET method, which is provably optimal. It is possible to integrate adaptivity on presorted data: Ducksort uses the POET instead of the DIET method: good in practice but no longer optimal.

75 years after John von Neumann’s Mergesort, we present stable algorithms that combine the buffer-locality of Quicksort with the generality of Mergesort. Instead of 100% distant buffer, Frogsort and Geckosort need only 50% (or less) local buffer. Furthermore they are automatically half-adaptive to presorted data, and we show how to achieve bi-adaptivity to pre-sorted and reverse-sorted data: Octosort and Squidsorts embrace existing order and only lazily enforce the desired order. Unlike natural Mergesorts such as Timsort which are optimized for the best case of full-presorting, the greeNsort^® algorithms are optimized for the worst case of real sorting work and can be parallelized to multiple CPU-cores. They also can be implemented for size-varying elements (unlike Quicksort, which incurs expensive random-access when used indirectly). Our low-memory algorithms Walksort and distance-reducing Jumpsort have lower Footprint than the impressive Grailsort and Sqrtsort of Astrelin, and hence allow resilient use of old hardware with little RAM.