marvinjames

Of course there was pressure, but why not just say that you know an algorithm that can do this faster, but you can't remember the name of it, and then just provide the intuition behind it?

Best case for heapsort is actually O(n). Build heap always takes O(n). Then e.g. when all keys are the same, the max-heapify call will take O(1) instead of O(logn).