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.

 

Advertisement

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s