heapsort
Heapsort sorts by leaning on a clever data structure: the binary heap. First it rearranges the array into a max-heap, a shape where every parent is at least as large as its children, so the biggest element bubbles to the top (the front of the array). Then it repeatedly swaps that top element to the end, shrinks the heap by one, and lets the heap repair itself — peeling off the largest remaining element each round until the array is sorted.
The neat part is that the heap lives inside the very same array, using index arithmetic (the children of position i sit at 2i+1 and 2i+2) instead of pointers. Building the heap takes O(n), and each of the n extract-max steps costs O(log n) to sift the new root back down to its correct level — the height of the heap.
Multiply and you get O(n log n) time in the best, average, and worst case alike — heapsort, like merge sort, has no bad inputs. Better still, it sorts in place with only O(1) extra space, unlike merge sort. Its weaknesses are that it is not stable, and its scattered, jumping memory access is less cache-friendly than quicksort's, so it's usually a touch slower in practice. It shines as a worst-case-safe backstop — which is exactly why introsort switches to heapsort when quicksort's recursion runs too deep.
void heapsort(std::vector<int>& a) {
std::make_heap(a.begin(), a.end()); // build max-heap, O(n)
for (auto end = a.end(); end != a.begin(); --end)
std::pop_heap(a.begin(), end); // move max to the back, O(log n)
} // array is now sorted ascendingn extractions x O(log n) sift-down each = O(n log n), in place with O(1) extra space.
Heapsort and merge sort are both guaranteed O(n log n); heapsort wins on space (O(1) in-place vs O(n)) but loses on stability (heapsort is unstable, merge sort is stable). C++ exposes the underlying machinery as std::make_heap, std::push_heap and std::pop_heap.