A framework for adaptive sorting

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

Ola Petersson, Alistair Moffat

Publication date: 6 June 1995

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

zbMATH Keywords

sorting algorithmpresortedness

Mathematics Subject Classification ID

Searching and sorting (68P10) Combinatorics of partially ordered sets (06A07) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (8)

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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

This page was built for publication: A framework for adaptive sorting