Heap sort's worst- and average-case running time are both provably within a constant factor of optimality (both in running time and number of comparisons), but it's either likely or straight up provably not actually optimal in any of the four categories.