Comment by Epa095

Usually when one talk about sorting, without specifying closer, one means comparison sort [1], which indeed has an average-case lower bound of O(n*log(n)). In more special cases all kinds of other runtimes are possible.

1: https://en.wikipedia.org/wiki/Comparison_sort