In: array

Out: sorted array

Суть алгоритма:

Строим макс-кучу, извлекаем из неё максимальный элемент обменом с последним и восстанавливаем макс-кучу после каждой такой операции, размер кучи уменьшается на 1 каждый раз.

void heapSort(int* array) {
	Heap heap = buildMaxHeapFromArray(array); 
	for (int i = n-1; i > 0; i--) {
		swap(heap[0], heap[i]);
	  heap.heapSize -= 1;
	  heap.siftDown(0);
	}
}

У Кормена нумерация массива с 1 🙂. Introduction to Algorithms (Fourth Edition) - Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein (2022)

Таким образом, справа налево у нас будет нарастать отсортированный массив.

Аналогично можно и с Min Heap проделать, алгоритм слегка изменится.

Complexity — $O(n\log{n})$

Если сортируем произвольный массив $O(n\log{n})$:

Построить макс-кучу из массива - $O(n\log{n})$, далее n-1 раз вызываем siftDown()

n*log(n) + (n-1)*log(n) = $O(n\log{n})$