array.sort()

Вы когда-нибудь задумывались как работает сортировка из-под капота?
Возможно, это Quick sort?
Возможно, Merge Sort?
А, возможно, собственная секретная разработка?

За всех говорить не могу, но расскажу о таком подходе как Introsort.

Introsort (Introspective sort) = QuickSort + HeapSort + InsertionSort
Алгоритм сортировки, предложенный Дэвидом Мюссером[англ.] в 1997 году
___

Зачем столько сложностей❓

Изначально применяется QuickSort, НО в худшем случае он даст O(n²). Такая ситуация может произойти при неудачном выборе pivot.
Пример: отсортированный массив + pivot - последний элемент.

Можно выбирать опорный элемент при помощи median-of-three (первый, средний, последний - выбираем средний по величине). Метод хорошо работает на большинстве входных данных, но возможно найти такие входные данные, которые сильно замедлят алгоритм сортировки.

Еще один минус QuickSort - рекурсия, а точнее возможное переполнение стека. Например, лимит 2 * log n (при нормальном разбиении глубина рекурсии примерно log n). Если глубина стала больше, разбиение плохое, а, следовательно, риск O(n²).
___

Если глубина рекурсии слишком большая, переключаемся на HeapSort.

HeapSort дает гарантированное O(n log n), но в среднем работает медленнее.
___

InsertionSort применяется, когда размер подмассива маленький (меньше 16 или 32 элементов).

Почему в игру вступает InsertionSort❓

• рекурсия и partition становятся дороже
• insertion sort быстрее на маленьких массивах
• insertion sort почти линейный на почти отсортированных данных
___

Тезисно:
✅ Introsort - инженерный компромисс между скоростью и гарантией.

✅ InsertionSort - оптимизация для маленьких массивов.
✅ HeapSort - защита от деградации.
✅ QuickSort - основная рабочая лошадь.