Optimal Incremental Sorting

Rodrigo Paredes and Gonzalo Navarro

Let A be a set of size m. Obtaining the first k <= m elements of A in ascending order can be done in optimal O(m + k*log k) time. We present an algorithm (online on k) which incrementally gives the next smallest element of the set, so that the first k elements are obtained in optimal time for any k. We also give a practical algorithm with the same complexity on average, which improves in practice the existing online algorithm. As a direct application, we use our technique to implement Kruskal's Minimum Spanning Tree algorithm, where our solution is competitive with the best current implementations. We finally show that our technique can be applied to several other problems, such as obtaining an interval of the sorted sequence and implementing heaps.