Fast and Simple Sorting Using Partial Information
OPEN ACCESS
Loading...
Author / Producer
Date
2024-07
Publication Type
Master Thesis
ETH Bibliography
yes
Citations
Altmetric
OPEN ACCESS
Data
Rights / License
Abstract
We consider the problem of sorting n totally ordered items by doing binary comparisons, given a list of m comparisons that have already been performed. This problem has been called sorting under partial information, and it has been intensely studied since 1976.
We propose a simple algorithm that solves this problem in O(log T) comparisons and O(log T + n + m) time, where T is the number of total orders consistent with the pre-existing comparisons. This is optimal up to constant factors. This problem has a long line of research, and for more than 30 years, all known solutions were either not polynomial, or relied on the ellipsoid method, which made them impractical. The best previous result achieves O(log T) comparisons in Θ(n^2.5) time and is more complicated.
Our result combines two standard algorithms: topological sorting, and heapsort with the right kind of heap. Our algorithm can be obtained by a one-line modification of the topological sorting algorithm, and its analysis is short and straightforward.
Permanent link
Publication status
published
External links
Editor
Contributors
Examiner : Steurer, David
Examiner: Haeupler, Bernhard
Book title
Journal / series
Volume
Pages / Article No.
Publisher
ETH Zurich
Event
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
sorting under partial information; heaps; data structures; Beyond worst-case analysis; Graph algorithms
Organisational unit
08730 - Gruppe Häupler / Group Häupler
Notes
Funding
Related publications and datasets
Is supplemented by: https://doi.org/10.48550/arXiv.2404.04552