Executive summary

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).


The greeNsort® story

Intro

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-dilemma

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-trilemma

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 greeNsort® paradigm

The new greeNsort® algorithms share a new paradigm for developing and evaluating sorting algorithms.

Footprint

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.

Distance

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.

Symmetry

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.


Call to action

The CO2-footprint of IT is increasing and contributes to global heating: contribute to more sustainable software.

Read

Beyond lots of info on this website we provide the following learning material:

Apply

This is what you can do, for more information see the Action|Apply menu:

  • check for sorting library calls in software that you maintain and consider using more efficient libraries such as IPS4o, Pdqsort or Skasort
  • check for sorting code in software that you maintain and consider using better algorithms such as radix-sort or greeNsort® algorithms
  • check for algorithmic teaching material that you maintain and consider integrating greeNsort® definitions, techniques and algorithms
  • check for programming languages or CPU-design that you maintain and consider integrating support for symmetric operations (bi-directional iterators, code-mirroring, etc.)

Certify

You can certify your software for greeNsort via self-certification or external certification, for more information see Notification and Certification:

  • notify us about your usage of greeNsort® algorithms via our email-API
  • email-notification is the basis for our forthcoming self-certification program that allows you to use our grey logo
  • let us know if you want consulting or full-certification for using our green logo
  • give us feedback about your experience with greeNsort® and improvement-suggestions


Indeed, I believe that virtually every important aspect of programming arises somewhere in the context of sorting or searching ― Donald E. Knuth1


  1. The Art of Computer Programming, Volume 3, Sorting and Searching↩︎

greeNsort brand logo

Copyright © 2010 - 2024 Dr. Jens Oehlschlägel - All rights reserved - Terms - Privacy - Impressum