Minimal mergesort.
Type of content
Reports
UC permalink
Publisher's DOI/URI
Thesis discipline
Degree name
Publisher
University of Canterbury. Computer Science and Software Engineering
Journal Title
Journal ISSN
Volume Title
Language
Date
1997
Authors
Takaoka, Tadao
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.
Description
Citation
Keywords
adaptivesort, minimal mergesort, ascending runs, entropy
Ngā upoko tukutuku/Māori subject headings
ANZSRC fields of research
Field of Research::08 - Information and Computing Sciences::0802 - Computation Theory and Mathematics::080201 - Analysis of Algorithms and Complexity
Rights
Copyright Tadao Takaoka