Quadratic Time Algorithms Appear to be Optimal for Sorting Evolving Data.

Juan Jos Besa Vial, William E. Devanny, David Eppstein, Michael T. Goodrich, Timothy Johnson

Browse the full ALENEX paper archive.