Sorting with Fibonacci Numbers and a Knuth Reward Check

The following incredibly small sorting algorithm has an $O(n^{4/3})$ worst-case runtime: def fibonacci_sort(v): a, b = 1, 1 while a * b < len(v): a, b = b, a + b while a > 0: a, b = b - a, a g = a * b for i in range(g, len(v)): while i >= g and v[i - g] > v[i]: v[i], v[i - g] = v[i - g], v[i] i -= g As the name implies, it uses the Fibonacci sequence ($1, 1, 2, 3, 5, \dots$) to sort the elements. In this article I will explain how it works, show an interesting divisibility property of the Fibonacci numbers and use that to prove its complexity. I will also explain how I ended up with one of Donald Knuth’s coveted reward checks. Shellsort The above sorting algorithm is an instance of the more generic Shellsort. Shellsort, named after Donald L. Shell, does not directly sort all the elements in one step. Rather, it first only sorts subsequences of the array in a process known as $k$-sorting. $k$-sorting A subsequence of an array can be any of its elements, but they must remain in the…