Heap Sort је један од алгоритама класе О(n log n). За разлику од Quick Sort-a и Merge Sort-a он не захтева рекурзије. Генерално Heap Sort је спорији од Quick и Merge Sort-a, али добар за сортирање великог сета података зато што не користи рекурзије. Такође, ако је низ делимично сортиран Heap Sort је бржи од Quick Sort-a.
Heap Sort ради као што му име сугерише. Прво, он формира бинарни heap од датог низа и поставља број елемената на број елемената у почетном низу. Онда он замењује први и задњи елемент heap-a, задњи еленент смешта на крај низа, смањује број елемената за један и спушта први елемент низ дрво све док је бар један његов потомак већи од њега. Тај процес се наставља док се величина heap-а не смањи на 2.
Предности: Не захтева рекурзије.
Мане: Спорији је од Quick и Merge Sort-a.