A sort of an adversary
2019
We describe an efficient deterministic adversary that forces any comparison-based sorting algorithm to perform at least [MATH HERE] n log n comparisons. This improves on previous efficient adversaries of Atallah and Kosaraju (1981), Richards and Vaidya (1988), and of Brodal et al. (1996) that force any sorting algorithm to perform at least 1/2n log n comparisons.
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
0
References
0
Citations
NaN
KQI