K-medoids clustering is one of the most popular techniques in exploratory data analysis. The most commonly used algorithms to deal with this problem are quadratic on the number of instances, n, and usually the quality of the obtained solutions strongly depends upon their initialization phase. In this work, we propose an algorithm for the K -medoids problem on the l_1-norm/Manhattan distance with a computational complexity of O(n⋅max{log n,K}⋅d) , along with theoretical guarantees in terms of the accuracy of the obtained approximation. In addition, we propose a cheap split-merge mechanism that can be used to re-start the proposed algorithm after its convergence to a fixed point. Under some mild assumptions, we prove that such a re-start procedure reduces the error of the given fixed point. The work also includes an extensive experimentation, in which we compare our method to the most popular approaches for the K -medoids problem: PAM, CLARA and Park's K -medoids. The obtained empirical results show the proposed algorithm to consistently converge to the solutions with the lowest errors, up to two orders of magnitude of relative error lower than the previously mentioned methods, while also requiring the lowest computational running times among them: up to three orders of magnitude lower.