How robust are average complexity measures? A statistical case study

In the present paper, the authors reject one of Knuth's well known results on average case complexity in replacement (i.e. selection) sort and hence challenge the robustness of average complexity measures where the response variable is sensitive to ties.