What is the first publication of the concept of optimizing merge sort by

  1. identifying sequences of consecutive positions in increasing orders (aka runs) in linear time; then
  2. repeatedly merging the two shortest such sequences and adding the result of this merging to the list of sorted fragments.

In some of my publications (e.g. http://barbay.cl/publications.html#STACS2009, http://barbay.cl/publications.html#TCS2013) I used this trick to sort faster and to generate a compressed data structure for permutation.

It seems that this trick was introduced before, just in the context of sorting faster, but neither me nor my student have been able to find back the reference?

  • did you check Knuth? I remember there's was quite a bit on run in TAOCP. – Mikolas Aug 9 '16 at 10:54
  • 1
    @Mikolas: I did, he mentions runs in his description of "natural merge sort" (page 160 of the tome 3 of the 3rd edition), but he analyzes its complexity only on average (which yields $n/2$ runs), not in function of the number $\rho$ of runs (it would yield $n(1+\lg\rho)$ comparisons), and even less so in function of the entropy of the sizes $(n_1,\ldots,n_\rho)$ of the runs (it would yield $n(1+2H(n_1,\ldots,n_\rho))$ comparisons). – Jeremy Aug 9 '16 at 20:17
  • In their survey "A survey of Adaptive Sorting Algorithms", Estivill Castro and Wood [1992], Mannila in 1985 proved that Natural Mergesort takes time within $O(n(1+lg(r+1)))$ to sort n elements forming r runs. But they do not take advantage of the relative lenghts of the runs. – Jeremy Aug 23 '16 at 11:25
up vote 9 down vote accepted

I found the result hidden in an obscure 4p technical report: I share my results here in case others are interested.

  1. Knuth mentions runs in his description of "natural merge sort" (page 160 of the tome 3 of the 3rd edition), but he analyzes its complexity only on average (which yields n/2 runs), not in function of the number ρ of runs
  2. in 1985, Mannila proved that Natural Mergesort takes time within O(n(1+lg(r+1))) to sort n elements forming r runs.
  3. in 1996, Tadao Takaoka (http://dblp.uni-trier.de/pers/hd/t/Takaoka:Tadao) introduced the notion of the entropy of the distribution of the sizes (n1,…,nρ) of the runs in an tech report 4 pages article titled "Minimal MergeSort", and proved a complexity of $n(1+2H(n1,…,nρ))$ comparisons
  4. in 2009, the technique was presented at the symposium Mathematical Fundation of Computer Science (along with results on sorting, shortest paths and minimum spanning trees).
  5. in 2010, it was published in the journal of Information Processing under the title "Entropy as Computational Complexity", with an added co-author, Yuji Nakagawa (https://www.semanticscholar.org/author/Yuji-Nakagawa/2219943).

I join the bibtex references below.

@TechReport{1997-TR-MinimalMergesort-Takaoka, author = {Tadao Takaoka}, title = {Minimal Mergesort}, institution = {University of Canterbury}, year = 1997, note = {http://ir.canterbury.ac.nz/handle/10092/9676, last accessed [2016-08-23 Tue]}, abstract = {We present a new adaptive sorting algorithm, called minimal merge sort, which merges the ascending runs in the input list from shorter to longer, that is, merging the shortest two lists each time. We show that this algorithm is optimal with respect to the new measure of presortedness, called entropy.} }

@InProceedings{2009-Chapter-PartialSolutionAndEntropy-Takaoka, author="Takaoka, Tadao", editor="Kr{\'a}lovi{\v{c}}, Rastislav and Niwi{\'{n}}ski, Damian", title="Partial Solution and Entropy", bookTitle="Mathematical Foundations of Computer Science 2009: 34th International Symposium, MFCS 2009, Novy Smokovec, High Tatras, Slovakia, August 24-28, 2009. Proceedings", year="2009", publisher="Springer Berlin Heidelberg", address="Berlin, Heidelberg", pages="700--711", isbn="978-3-642-03816-7", doi="10.1007/978-3-642-03816-7_59", url="http://dx.doi.org/10.1007/978-3-642-03816-7_59", abstract = {If the given problem instance is partially solved, we want to minimize our effort to solve the problem using that information. In this paper we introduce the measure of entropy H(S) for uncertainty in partially solved input data S(X) = (X 1, ..., X k ), where X is the entire data set, and each X i is already solved. We use the entropy measure to analyze three example problems, sorting, shortest paths and minimum spanning trees. For sorting X i is an ascending run, and for shortest paths, X i is an acyclic part in the given graph. For minimum spanning trees, X i is interpreted as a partially obtained minimum spanning tree for a subgraph. The entropy measure, H(S), is defined by regarding p i  = |X i |/|X| as a probability measure, that is, H(S)=−nΣki=1pilogpi, where n=Σki=1|Xi|. Then we show that we can sort the input data S(X) in O(H(S)) time, and solve the shortest path problem in O(m + H(S)) time where m is the number of edges of the graph. Finally we show that the minimum spanning tree is computed in O(m + H(S)) time.} }

@article{2010-JIP-EntropyAsComputationalComplexity-TakaokaNakagawa, author = {Tadao Takaoka and Yuji Nakagawa}, title = {Entropy as Computational Complexity}, journal = jip, volume = {18}, pages = {227--241}, year = {2010}, url = {http://dx.doi.org/10.2197/ipsjjip.18.227}, doi = {10.2197/ipsjjip.18.227}, timestamp = {Wed, 14 Sep 2011 13:30:52 +0200}, biburl = {http://dblp.uni-trier.de/rec/bib/journals/jip/TakaokaN10}, bibsource = {dblp computer science bibliography, http://dblp.org}, abstract = {If the given problem instance is partially solved, we want to minimize our effort to solve the problem using that information. In this paper we introduce the measure of entropy, H (S), for uncertainty in partially solved input data S (X) = (X1, . . . , Xk), where X is the entire data set, and each Xi is already solved. We propose a generic algorithm that merges Xi's repeatedly, and finishes when k becomes 1. We use the entropy measure to analyze three example problems, sorting, shortest paths and minimum spanning trees. For sorting Xi is an ascending run, and for minimum spanning trees, Xi is interpreted as a partially obtained minimum spanning tree for a subgraph. For shortest paths, Xi is an acyclic part in the given graph. When k is small, the graph can be regarded as nearly acyclic. The entropy measure, H (S), is defined by regarding pi = ¦Xi¦/¦X¦ as a probability measure, that is, H (S) = -n (p1 log p1 + . . . + pk log pk), where n = ¦X1¦ + . . . + ¦Xk¦. We show that we can sort the input data S (X) in O (H (S)) time, and that we can complete the minimum cost spanning tree in O (m + H (S)) time, where m in the number of edges. Then we solve the shortest path problem in O (m + H (S)) time. Finally we define dual entropy on the partitioning process, whereby we give the time bounds on a generic quicksort and the shortest path problem for another kind of nearly acyclic graphs.}
}

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.