Sorting, Information, and Recursion

I’ve updated the paper that discusses some of the recent results I’ve proved on this blog, to include heavily annotated code, given that there seems to have been some confusion about the runtime of the algorithms on reddit.

The results prove that (1) a list is sorted if and only if the distance between adjacent entires is minimized, and (2) a list is sorted if and only if an encoding of the list as a particular class of recurrence relation minimizes information. These results together demonstrate an equivalence between sorting and minimizing information, which is in my opinion, non-obvious. I also introduced what I believe to be the fastest known sorting algorithms, one with an $O(N)$ runtime, and another with an $O(\log(N))$ runtime, both of which are already faster than the lower bounds of $O(n\log(n))$ for serial sorting algorithms (both algorithms are parallel). The code for both are attached to the paper linked to above, which you can also find below.