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 - основная рабочая лошадь.
