Get the latest tech news
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.
None
Or read this on Hacker News
