The performance of Heapsort algorithms on arbitrary input is examined. It is proved that annlogn−O(n)lower bound on the number of comparisons holds for a set of Heapsort algorithms, including Williams-Floyd's algorithm, Carlsson's bottom-up linear or binary insertion algorithm, and all up-down algorithms, on any inpu
展开▼
