A framework for adaptive sorting

DOI10.1016/0166-218X(93)E0160-ZzbMath0827.68032MaRDI QIDQ1891925

Alistair Moffat, Ola Petersson

Publication date: 6 June 1995

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

sorting algorithm; presortedness

Mathematics Subject Classification ID

68P10: Searching and sorting

06A07: Combinatorics of partially ordered sets

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

Chunky and equal-spaced polynomial multiplication, Efficient sample sort and the average case analysis of PEsort, Presorting algorithms: an average-case point of view, LRM-trees: compressed indices, adaptive sorting, and compressed permutations, The analysis of evolutionary algorithms on sorting and shortest paths problems, Sublinear merging and natural mergesort, Adaptive sorting: an information theoretic perspective, From Time to Space: Fast Algorithms That Yield Small and Fast Data Structures

Cites Work

• Encroaching lists as a measure of presortedness
• Smoothsort, an alternative for sorting in situ
• Splitsort -- an adaptive sorting algorithm
• How good is the information theory bound in sorting?
• Sorting shuffled monotone sequences
• A new measure of presortedness
• Sublinear merging and natural mergesort
• Measures of Presortedness and Optimal Sorting Algorithms
• Sorting, trees, and measures of order
• Exploiting partial order with Quicksort
• HISTORICAL SEARCHING
• Adaptive Heapsort
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item