A sort of an adversary

Haim Kaplan, Or Zamir, Uri Zwick

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...

Figure