Before revision:  The first algorithm is  randomized and matches the O(m \log m) runtime of the  algorithm by Cardinal and Iacono.
After revision:  The first algorithm is randomized and matches the O(m \log m) runtime of the Las-Vegas algorithm by Cardinal and Iacono.