Сравнение разных сортировок (heap, merge, quick, introsort, insertion, selection)

reverse за $O(n)$, rotate за $O(n)$, sort за $O(nlogn)$, stable sort за $O(n^2)$.

inplace-merge: стабильный за $O(n+m^{1+eps})$, стабильный за $O(nlogn)$, нестабильный за $O(n)$

merge-sort: нерекурсивная версия за $O(nlogn)$, inplace версия за $O(nlog^2n)$

BlockSort: buffer extraction + sort blocks + local merges

Обзор структур данных без доп.памяти: heap, k-heap, min-max-heap, fenwick-tree, beap