Measures of Presortedness and Optimal Sorting Algorithms

DOI10.1109/TC.1985.5009382zbMath0556.68031MaRDI QIDQ3219783

Heikki Mannila

Publication date: 1985

Published in: IEEE Transactions on Computers (Search for Journal in Brave)

zbMATH Keywords

sorting; presortedness; insertion sort algorithm

Mathematics Subject Classification ID

68P10: Searching and sorting

Related Items

Computing and ranking measures of presortedness, Unnamed Item, Sorting shuffled monotone sequences, A framework for adaptive sorting, On compressing permutations and adaptive sorting, A note on adaptive parallel sorting, Recursive merge sort with erroneous comparisons, On partitions and presortedness of sequences, Sorting roughly sorted sequences in parallel, Computing inversion pair cardinality through partition-based sorting, An optimal parallel adaptive sorting algorithm, Splitsort -- an adaptive sorting algorithm, Arranging \(n\) distinct numbers on a line or a circle to reach extreme total variations, Right invariant metrics and measures of presortedness, Exploiting few inversions when sorting: Sequential and parallel algorithms, Measures of distinctness for random partitions and compositions of an integer, Presorting algorithms: an average-case point of view, A new measure of presortedness, A framework for adaptive sorting, Exact and approximation algorithms for sorting by reversals, with application to genome rearrangement, A selectable sloppy heap, Sublinear merging and natural mergesort, A machine learning approach to algorithm selection for \(\mathcal{NP}\)-hard optimization problems: a case study on the MPE problem, Adaptive sorting: an information theoretic perspective, An adaptive generic sorting algorithm that uses variable partitioning^∗, From Time to Space: Fast Algorithms That Yield Small and Fast Data Structures, Badness of Serial Fit Revisited, Partial Solution and Entropy, Randomized adaptive sorting