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

Так, слушай сюда, про этот ваш sort() в JavaScript. Ты думаешь, там всё просто, нажал кнопку — и порядок? Хуй там, блядь!

Вот смотри, в нормальных движках, типа того, что в Хроме или Ноде, работает TimSort. Умный алгоритм, ёпта. В мозглявом Фаерфоксе — MergeSort. Но суть-то одна: в среднем всё летает за O(n log n), это как надо.

Но есть нюанс, блядь! Есть же худший случай, O(n^2), когда всё накрывается медным тазом. Правда, это бывает редко, как честный политик, но теоретически возможно. Движки стараются, чтобы такого не было, но подозрение, блядь, чувствую — где-то эта хуйня притаилась.

Вот тебе пример, смотри:

const arr = [5, 3, 8, 1];
arr.sort(); // O(n log n) в типичном сценарии

Вроде всё ок? Ан нет! Если ты числа так сортируешь, то получишь лексикографический пиздец. '10' окажется перед '2', потому что строки, блядь! Ядрёна вошь!

Поэтому всегда, сука, передавай компаратор, если работаешь с цифрами:

arr.sort((a, b) => a - b); // правильная сортировка чисел

Вот теперь да, красота.

А теперь главное: если у тебя массив размером с овердохуища, скажем, 10 тысяч элементов и больше, — начинай думать головой. Сложность-то не хуёвая. В 99% случаев родной sort() справится, но бывают такие извращённые данные, что ручная реализация, например, QuickSort, может оказаться шустрее. Но это уже высший пилотаж, на грани фола.

Короче, запомни: sort() — он не дурак, но и ты не будь мудаком, передавай функцию сравнения для чисел. И всё будет пучком.