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 Monte-Carlo randomized and matches the O(m \log m) runtime of the algorithm by Cardinal and Iacono.