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
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.