The dynamic partial sorting problem asks for an algorithm that maintains lists of numbers under the link, cut and change value operations, and queries the sorted sequence of the k least numbers in one of the lists. We examine naive solutions to the problem and demonstrate why they are not adequate.
Then, we solve the problem in O(k log(n)) time for queries and O(log(n)) time for updates using the tournament tree data structure, where n is the number of elements in the lists. We then introduce a layered tournament tree data structure and solve the same problem in O(log '(n) k log(k)) time for queries and O(log2(n)) for updates, where ' is the golden ratio and log '(n) is the iterated logarithmic function with base '. We then perform experiments to test the performance of both structures, and discover that the tournament tree has better practical performance than the layered tournament tree. We discuss the probable causes of this.
Lastly, we suggest further work that can be undertaken in this area.
