language-icon Old Web
English
Sign In

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
    []