Heap sort

Related terms

• Binary heap — A complete binary tree stored in a slice where every parent is not larger than its children; the minimum is always at index 0.
• Heapify — Turning an unordered slice into a heap in place in O(n), by sifting down from the last parent to the root.
• Quicksort — Pick a pivot, partition the slice around it, then sort both sides recursively; O(n log n) on average, in place.
• Merge sort — Split in half, sort each half, merge the two sorted halves; always O(n log n), stable, but needs O(n) extra memory.

← All terms