"We had a spat over complexity of Heapify function - He had opinion it works in O(nlogn). !!! I explained the Heapify and heapsort to him, in process I might have hurt his ego. !" Wonder if this candidate fell into a trap here... Heapify implementation via siftDown is O(n), but via siftUp is O(nlogn). Heapsort is O(nlogn) as well.