Is it possible for Heapsort to work in time $o(n\log n)$ on certain inputs?
For example in case of Insertion sort it is possible, however when it comes to Quickssort it is not possible. What about Heapsort? I tried to find an input array such that Heapsort will be working in $o(n\log n)$.
I ask you is it possible? Some permutation? The same elements?