How inefficient can a sort algorithm be?

Direct link to paper: https://arxiv.org/pdf/1406.1077v1