Abstract

We explored an uncharted part of the solution space for sorting algorithms: the role of symmetry in divide&conquer algorithms. We found/designed novel simple binary Quicksort and Mergesort algorithms operating in contiguous space which achieve improved trade-offs between worst-case CPU-efficiency, best-case adaptivity and RAM-requirements. The greeNsort® algorithms need less hardware (RAM) and/or less energy (CPU) compared to the prior art. The new algorithms fit a theoretical framework: Footprint KPIs allow to compare algorithms with different RAM-requirements, a new definition of sorting API-targets simplifies construction of stable algorithms with mirrored scan directions, and our ordinal machine model encourages robust algorithms that minimize access distance. Unlike earlier Quicksorts, our Zacksort, Zucksort and Ducksort algorithms optimally marry CPU-efficiency and tie-adaptivity. Unlike earlier Mergesorts which required 100% distant buffer, our Frogsort and Geckosort algorithms achieve similar CPU-efficiency with 50% or less local buffer. Unlike natural Mergesorts such as Timsort which are optimized for the best case of full-presorting, our Octosort and Squidsort algorithms achieve excellent bi-adaptivity to presorted best-cases without sacrificing worst-case efficiency in real sorting tasks. Our Walksort and Jumpsort have lower Footprint than the impressive low-memory Grailsort and Sqrtsort of Astrelin. Given the current climate-emergency, this is a call to action for all maintainers of sorting libraries, all software-engineers using custom sorting code, all professors teaching algorithms, all IT professionals designing programming languages, compilers and CPUs: check for better algorithms and consider symmetric code-mirroring.