Причина, по которой сортировка выбором работает за квадратичное время — это линейный поиск минимума на каждом шаге.
Чтобы соптимизировать время работы алгоритма, мы можем завести специальную структуру данных, которая поддерживает быстрое извлечение минимума из набора неупорядоченных элементов, добавить весь исходных массив в неё, а затем по одному извлекать минимум в новый отсортированных массив.
Это ровно то, что делает двоичная куча — за $O(\log n)$ на операцию. Воспользовавшись ей, получаем алгоритм, работающий за $O(n \log n)$:
void heapsort(int* a, int n) {
// копируем массив в кучу
t_n = n;
copy(a, a + n, t + 1);
build_heap();
for (int i = 1; i <= n; i++) {
// удаляем минимум, он останется в ячейке t[n + 1 - i]
swap(t[1], t[n + 1 - i]);
t_n--;
sift_down(1);
}
// получили массив t[1..n], в котором все элементы упорядочены по убыванию
reverse(t, t + n + 1);
copy(t, t + n, a);
}
Примечательно, что в случае «почти отсортированного» массива алгоритм можно немного ускорить. Если гарантируется, что каждый элемент находится на расстоянии не более $k$ от своей позиции в отсортированном массиве, то нам достаточно поддерживать кучу размера $O(k)$, считать массив «окном» из $k$ элементов, и после добавления очередного элемента выписывать минимум. Такой алгоритм будет работать за $O(n \log k)$.