Heapsort for sorted input
Time complexity of heapsort is $O(n \log n)$ for all types of input. If we have all input we need $O(n)$ time to build the max-heap. Then for sorting the the data, we need to remove the first element of the array then heapify the remaining data and repeat it for $n$ times. Which the act of heapifying for all steps needs $O(n \log n)$ time.