Future work

Algorithms

We expect that it is possible to make IPS4o stable using the permutation logic of our Walksort. We suspect, Squidsort could be made even more adaptive by replacing the static splits by searching for a optimal splitting point as in Peeksort. For elements of varying size that have no easily searchable separator like the null-terminator in strings, versions of Frogsorts should be developed which use pointers to elements (for direct sorting). Finally, we believe that parallel Frogsorts 2,3,6 can be written using predefined chunks with a fixed number of data and buffer elements. Beyond sorting, we would not be surprised, if the symmetric recursion and particularly Divide&Conquer with buffer could be used to design other algorithms, e.g. clustering.

Sorting APIs

Current sorting APIs limit the efficiency of sorting, for example C’s library (Quicksort) expects a ternary comparison function (using two binary comparisons under the hood), where an API expecting a binary comparison function would allow to sort with less comparisons. Optimal sorting APIs is an under-explored topic.

Code-Mirroring

In the testbed we have mirrored code sections by hand. In order to reduce the manual work of code-mirroring and to make errors less likely, code-mirroring could be done in meta-programming or programming languages accompanied with IDEs that support code-mirroring. In order to reduce binary code size, we envision code-mirroring CPU-instructions and compiler support. This is a promising novel field of research.