A fast natural algorithm for searching

AbstractIn this note we present two natural algorithms—one for sorting, and another for searching a sorted list of items. Both algorithms work in O(N) time, N being the size of the list. A combination of these algorithms can search an unsorted list in O(N) time, an impossibility for classical algorithms. The same complexity is achieved by Grover's quantum search algorithm; in contrast to Grover's algorithm which is probabilistic, our method is guaranteed correct. Two applications will conclude this note