Какая алгоритмическая сложность при сортировке массива в JavaScript

Вопрос выглядит как обычный вопрос про Big O, но на интервью в нем есть ловушка. У метода Array.prototype.sort в JavaScript нет одной гарантированной алгоритмической сложности, прописанной как часть языка. ECMAScript описывает поведение метода, но не говорит, какой алгоритм обязан использовать движок.

Можно ответить так:

В общем случае я ожидаю около O(n log n) для больших массивов в современных движках, но точный алгоритм и точная сложность зависят от реализации. В прикладном frontend-коде я не опираюсь на конкретный алгоритм. Я слежу за comparator, мутацией и объемом данных.

Такой ответ показывает, что вы знаете Big O и не выдаете деталь реализации за правило языка.

Если не передать compare-функцию, sort приводит элементы к строкам и сравнивает их в строковом порядке. Для строк это часто выглядит ожидаемо. Для чисел это почти всегда источник бага.

const numbers = [10, 2, 1];

// Плохо: сортировка как строк
numbers.sort();
console.log(numbers); // [1, 10, 2]

Безопаснее явно описать порядок:

const numbers = [10, 2, 1];

const sorted = [...numbers].sort((a, b) => a - b);
console.log(sorted); // [1, 2, 10]

Практический вывод простой: если вы сортируете не простые строки, почти всегда нужен comparator. Так вы защищаете UI от неверного порядка цен, рейтингов, дат и числовых колонок. Comparator должен быть чистой функцией. Не меняйте элементы, не пишите в store, не отправляйте аналитику и не делайте запросы из сравнения.

sort сортирует массив на месте и возвращает тот же массив. Это нормально для локальной одноразовой переменной, но опасно для данных из state, props, store или кеша. Последствия в UI: список может поменяться без явного обновления state, соседний компонент увидит уже мутированные данные, а мемоизация по ссылке перестанет защищать от лишней работы.

function Products({ products }) {
  // Плохо: мутирует props
  const sorted = products.sort((a, b) => a.price - b.price);

  return sorted.map((product) => <ProductCard key={product.id} product={product} />);
}

Исправление простое. Сначала создайте новый массив. Если сортировка тяжелая и зависит от одних и тех же входных данных, результат можно мемоизировать.

function Products({ products }) {
  const sorted = useMemo(
    () => [...products].sort((a, b) => a.price - b.price),
    [products]
  );

  return sorted.map((product) => <ProductCard key={product.id} product={product} />);
}

Если ваша целевая среда поддерживает toSorted, можно использовать его как немутирующую альтернативу. Но на интервью все равно полезно проговорить, что поддержка среды и транспиляция имеют значение.

O(n log n) может звучать нормально, пока массив небольшой. Но сортировка идет синхронно в основном потоке. Если элементов много или comparator дорогой, пользователь увидит лаги. Это может быть задержка ввода, рывки скролла или зависание фильтров.

Частая ошибка: делать тяжелую работу внутри comparator.

// Плохо: Date.parse вызывается много раз во время сортировки
const sorted = [...events].sort(
  (a, b) => Date.parse(a.startedAt) - Date.parse(b.startedAt)
);

Лучше заранее подготовить ключи сортировки, если данных много или сортировка повторяется.

const withSortKey = events.map((event) => ({
  event,
  startedAtMs: Date.parse(event.startedAt),
}));

const sorted = withSortKey
  .sort((a, b) => a.startedAtMs - b.startedAtMs)
  .map(({ event }) => event);

Это не отменяет сложность сортировки, но снижает цену каждого сравнения. Для очень больших списков стоит думать о серверной сортировке, пагинации, виртуализации или Web Worker. Не переносите в comparator запросы за дополнительными данными: он может вызваться десятки или тысячи раз, что даст лишнюю нагрузку, race condition и неверную аналитику.