What is the time complexity of heap sort?

Best case O(n log n). Average case O(n log n). Worst case O(n log n). Space complexity is O(1). Building the heap is O(n); each of the n extractions costs O(log n).

Heap sort

medium

The tree and the array below it are the same memory - watch a swap change both at once. The only sort here with an O(n log n) guarantee and O(1) extra space.

Best O(n log n)Average O(n log n)Worst O(n log n)Space O(1)Not stableIn place

Loading the heap sort engine…

Where to go next

Binary heap

medium

An array pretending to be a tree.

Quick sort

medium

Partition around a pivot, then recurse on both halves.

Selection sort

easy

Find the minimum, move it to the front, repeat.