Алгоритмы сортировки имеют асимптотическую сложность O(n log n), потому что при увеличении размера входных данных время выполнения алгоритма увеличивается гораздо медленнее, чем линейно. 3

Сложность O(n log n) означает, что при больших n время работы алгоритма (или общее количество операций) не более чем C · n log n, где C — некая положительная константа. 1 Чем сложнее алгоритм и чем более продвинутые структуры данных в нём используются, тем большее количество операций необходимо выполнить при исполнении программы для поддержки всех нужных переменных и структур. 1 То есть больше коэффициент C и реальное время работы. 1

Например, сортировка быстрым методом (quick sort) в среднем случае имеет сложность O(n log n), но в худшем случае — O(n²). 3