On partitions and presortedness of sequences (Q808689)

To take advantage of existing order in a sequence when sorting, we evaluate the quantity of this information by the minimal size of decomposition of the input sequence, particularly the minimal size of chain and of monotonic partitions. Some sorting strategies that are optimal with respect to these measures of presortedness are presented. The relationships between these new measures of presortedness and other known measures have also been explored. As an application, we carry out the optimality of a adaptive sorting algorithm Skiena's Melsort. For some special partitioning strategies, we present two sorting algorithms based on Dijkstra's Smoothsort. Moreover, the optimalities of these two algorithms are demonstrated. By examining the optimalities of sorting algorithms with respect to certain measures of presortedness, we propose also some optimal sorting strategies for one class of measures. Finally, we discuss other types of sorting problems, such as sorting multisets and topological sorting. In particular, we derive an optimal algorithm for sorting multisets and for finding the multiset sizes as well.