A sort of an adversary
Lists
Only you see this
Abstract
We describe an efficient deterministic adversary that forces any comparison-based sorting algorithm to perform at least 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 ψn log n comparisons.
BibTeX
@inproceedings{kaplan2019sort,
author = {Haim Kaplan and Or Zamir and Uri Zwick},
title = {{A sort of an adversary}},
booktitle = {SODA},
year = {2019},
doi = {10.1137/1.9781611975482.79},
}Loading related content...