Minimal mergesort. (1997)
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.
Keywordsadaptivesort; minimal mergesort; ascending runs; entropy
ANZSRC Fields of Research08 - Information and Computing Sciences::0802 - Computation Theory and Mathematics::080201 - Analysis of Algorithms and Complexity
RightsCopyright Tadao Takaoka
Showing items related by title, author, creator and subject.
Nakagawa, Y.; James, R.J.W.; Rego, C.; Edirisinghe, C. (University of Canterbury. Management, Marketing, and Entrepreneurship, 2014)This paper develops a new way to help solve difficult linear and nonlinear discrete-optimization decision models more efficiently by introducing a problem-difficulty metric that uses the concept of entropy from information ...
Oo, C. H. (University of Canterbury. Computer Science, 1978)The Dantzig-Wolfe decomposition (linear programming) principle published in 1960 involves the solving of large-scale mathematical programming problems of particular structure. Large practical problems of this type typically ...
Xu, R.; Morris, K.A.; Woodward, G.K.; Kocak, T. (University of Canterbury. Electrical and Computer Engineering, 2012)Sequential decoding can achieve a very low computational complexity and short decoding delay when the signal- to-noise ratio (SNR) is relatively high. In this paper, a low-complexity high-throughput decoding architecture ...