Recall that to sort
n
elements with a comparison-based algorithm requires
(
n
log
n
) time.
(n log n) time.