Here you learn about novel simple (and beautiful) 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 (for better robustness and resilience).
Sorting is the foundation for many algorithms in IT. Hence sorting consumes lots of computer hardware and energy. And sorting sucks, because its costs grow more than linearly with the size of the sorting problem. While the most efficient sorting algorithms are complex k-ary algorithms, simple binary sorting is used in many places and simple binary sorting is the foundation for teaching algorithms. The greeNsort® project analyzed the history of sorting algorithms, identified biased turns in the history of sorting, and developed a new approach to binary sorting in contiguous space: Simple Symmetric Sustainable Sorting.
Quicksort – published 1961 by Tony Hoare – has an interesting history: it proved to be successful, robustly across decades of changing hardware although, despite of it’s seeming simplicity, it turned out to be difficult to implement and never achieved the design goals of its inventor. Our research identifies a cardinal error in the history of Quicksort whose effects persist to this day. We present alternative solutions with better trade-offs between worst-case efficiency and best-case efficiency for data with duplicates. Our Zacksort, Zucksort and Ducksort are those algorithms, Tony Hoare had in mind when he wrote down Quicksort1. This innovation extends into improved partial sorting, selection and stable partitioning.
Mergesort – invented 1945 by John von Neumann – is more general than Quicksort, but never achieved Quicksorts memory-parsimony and cache-friendliness. Our research identifies a misunderstanding in the way John von Neumann’s mathematical algorithm was realized in von Neumann machines with virtual memory. We show that Mergesort algorithms can be designed to mimic the cache-friendliness of Quicksort and can reduce its memory-requirements substantially, hence marry the best of both worlds. The new stable Frogsort and Geckosort, Octosort and Squidsort, and Walksort and Jumpsort algorithms provide new interesting trade-offs between worst-case CPU-efficiency, best-case adaptivity to presorted data and RAM-requirements. The memory-management innovations in merging extend into stable partitioning, sorting long records with short keys and sorting elements of varying size.
The new greeNsort® algorithms share a new paradigm for developing and evaluating sorting algorithms.
Our new Footprint measure allows fair comparison of sustainability of algorithms with different memory-needs: by multiplying traditional CPU-cost with RAM-requirements. A surprising result is that the lowest footprints are achieved by algorithms with a moderate memory investment: neither 100% buffer nor the holy grail of inplace sorting are optimal.
Our algorithms are designed – like Quicksort – to reduce the move-distance in contiguous space. This simple design-principle assumes not more than a non-monotonic relationship between distance and cost. We call this the ‘ordinal machine model’, in other words: like John von Neumann and Anthony Hoare we focus on algorithm design, not on mathematical proofs gives a little-realistic particular machine model. We hope that the resulting algorithms behave robust across different (and unknown) hardware architectures.
The by far most important secret ingredient of our algorithms is their approach to symmetry in asymmetric contexts. By asymmetric contexts we mean the asymmetric features of von Neumann machines as well as asymmetric tasks such as MECE partitioning. Symmetric (mutual) recursion is the key to the new algorithms, supported by a new symmetric definition of sorting that extends the classic definition in Donald Knuth’s epochal work The Art of Computer Programming. Stepping back from the particular problem of sorting, we find it surprising, that differing from other sciences and arts, symmetry is not a core engineering principle in computer science. Further exploring symmetry may yield positive surprises in the design of programming languages, compilers and processors.
The CO2-footprint of IT is increasing and contributes to global heating: contribute to more sustainable software.
Beyond lots of info on this website we provide the following learning material:
This is what you can do, for more information see the Action|Apply menu:
You can certify your software for greeNsort via self-certification or external certification, for more information see Notification and Certification:
Indeed, I believe that virtually every important aspect of programming arises somewhere in the context of sorting or searching ― Donald E. Knuth1
The Art of Computer Programming, Volume 3, Sorting and Searching↩︎