This work looks promising, but it's important to note that the authors didnt prove worst case time complexity.

This algorithm can get much, much slower than O(n)