Какие знаешь алгоритмы синтетической сложности быстрее алгоритма быстрой сортировки

Для небольших массивов (до ~20 элементов) сортировка вставками (Insertion Sort) может быть быстрее QuickSort из-за меньших накладных расходов.

Для почти отсортированных данных TimSort (гибрид MergeSort + Insertion Sort, используется в Python) эффективнее QuickSort благодаря адаптивности.

Если элементы ограниченного диапазона (например, целые числа), Counting Sort или Radix Sort работают за O(n), что быстрее O(n log n).

Пример Counting Sort:

def counting_sort(arr, max_val):
    counts = [0] * (max_val + 1)
    for num in arr:
        counts[num] += 1
    sorted_arr = []
    for num, count in enumerate(counts):
        sorted_arr.extend([num] * count)
    return sorted_arr

Важно: выбор алгоритма зависит от данных. QuickSort доминирует в общем случае из-за средней O(n log n) и оптимизаций (например, выбор опорного элемента).