As presented, heapsort is efficient. Unlike the other sorts considered, which are array- or list-oriented, it is tree-oriented. They are O(n2) in the worst case, whereas heapsort is O(n lg n). Moreover, we shall see in Section 8.7 that it gives uniformly good sort times, no matter how ordered or unordered the original data. Although times are somewhat faster when the data is initially either fairly well ordered or reverse ordered, the range of these times is small compared to the other sorts. This is to be expected, since the construction of the heap takes little time and the reheaping tends to destroy any order present in the data. In effect it appears to be in random order. Actually, during reheaping, when shift works on larger entries at the root, it takes O(lg n) time, since they tend toward the bottom of the tree, while the opposite is true for smaller entries. Because most entries are near the bottom of the tree and are larger, their shifting makes up the bulk of the sorting time. Thus this time should be relatively insensitive to initial order in the data. This uniformity of sort times is one of its main virtues, since it eliminates the great variation in time from O(n) to O(n2) of the other sorts. In addition, it is fast.