Какая сложность сортировки списка?

Сложность сортировки списка зависит от алгоритма: эффективные (быстрая, слиянием, встроенный `sort`) — O(n log n), простые (пузырьком, вставками) — O(n²).

Зависит от алгоритма

Эффективные — O(n log n)

• Быстрая (quicksort) — O(n log n) в среднем, O(n²) в худшем.
• Слиянием (merge sort) — O(n log n) всегда, но O(n) памяти.
• Пирамидальная (heap sort) — O(n log n).

O(n log n) — теоретический предел для сортировок сравнением.

Простые — O(n²)

• Пузырьком, вставками, выбором — O(n²) (вложенные циклы). Для малых данных или учебные.

Специальные — O(n)

• Подсчётом (counting), поразрядная (radix) — O(n) для целых в ограниченном диапазоне (без сравнений).

Встроенный Array.prototype.sort

В V8 — Timsort (гибрид merge + insertion):

arr.sort((a, b) => a - b); // O(n log n), стабильная

• O(n log n) в среднем и худшем.
• Стабильная (с ES2019).
• Эффективна на частично отсортированных данных.

Что влияет на выбор

• Размер данных, память (merge требует O(n)), нужна ли стабильность, тип данных (radix для целых).

Коротко для собеседования

Сложность сортировки зависит от алгоритма: эффективные (quicksort, merge sort, heap sort) — O(n log n) (предел для сортировок сравнением); простые (пузырёк, вставки) — O(n²); специальные (counting, radix) — O(n) для целых. Встроенный Array.sort — Timsort, O(n log n), стабильный.