Heapsort

Why it costs this much

Building a heap takes O(n), then removing the extreme item n times costs O(log n) each.

Code

import heapq
def heap_sort(items):
    h = list(items)
    heapq.heapify(h)                                   # O(n)
    return [heapq.heappop(h) for _ in range(len(h))]   # n pops x O(log n)
# Textbook heapsort does the same work in place with O(1) extra space.

Common pitfalls

Heapsort is not stable and has poor cache behavior, so it is often slower than quicksort in practice.

Operation by operation

Heapsort. In place. Not stable. Slower in practice than quicksort because of poor cache locality.