What is the running time of heapsort when the input array is in increasing order? How about decreasing order? (I came across these questions in CLRS.)
Here is what I have done so far ...
For the increasing order (i.e. the order opposite to the output order) I am completely stuck and haven't been able to make any progress because as I see it as soon as we build the max heap the structure completely changes and I cant reason about what the final heap will look like.
For the decreasing case I feel like I understand what is going on and will try to describe that below, but its also a long way from a proof. A decreasing array is already a max heap so the array is unchanged by building the max heap. WLOG assume a complete binary tree (else just remove some elements until you get one)
Remove the first $n/4$ largest elements. The first element will then be lifted to the top and fall back down a distance of $\log n$ falling to the left each time (the left element is always the largest).
But now the right is larger for each vertex that this last element fell through. So the next vertex will first fall right then fall left the rest of the way. No vertex will fall the same path until this has been rectified. So elements moved to the top of the tree continue to fall the full length of the tree. Rectifying the tree seems like it will take a linear time because it has length logn and it feels like you have to go down a constant fraction of the other routes before it is done. But this is really wordy and sort of garbage.
I apologise if this could be written better but I tried my best to say what I mean.
Note I have read the proof for the general best case but I was looking for something more straightforward due to the extra information.
Thanks