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

Алгоритмы, быстрее Quicksort в определённых случаях

Quicksort имеет O(n log n) в среднем, но O(n квадрат) в худшем случае. Есть алгоритмы, которые лучше.

1. Merge Sort — гарантирована O(n log n)

Отличается от Quicksort тем, что всегда работает за O(n log n), даже в худшем случае.

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

Преимущества: гарантированное O(n log n), устойчива (stable). Недостатки: требует O(n) памяти, на практике медленнее Quicksort.

2. Heapsort — гарантирована O(n log n)

Использует структуру данных heap (куча).

Преимущества: O(n log n) гарантировано, O(1) дополнительная память. Недостатки: на практике медленнее, не устойчив, плохая кеш-локальность.

3. Introsort — гибрид Quicksort и Heapsort

Начинает с Quicksort, но если глубина рекурсии слишком большая, переходит на Heapsort.

Преимущества: O(n log n) гарантировано, скорость Quicksort в среднем. Используется в Python sorted() и C++ std::sort.

4. Counting Sort — O(n + k) для целых чисел

def counting_sort(arr, max_val):
    count = [0] * (max_val + 1)
    for num in arr:
        count[num] += 1
    result = []
    for i in range(max_val + 1):
        result.extend([i] * count[i])
    return result

Когда использовать: целые числа в известном диапазоне, диапазон мал. Пример: сортировка оценок 0-100.

5. Radix Sort — O(d * n) для целых чисел

Сортирует по цифрам (разрядам).

Когда использовать: целые числа с фиксированным количеством цифр, очень большие наборы данных.

6. Bucket Sort — O(n + k) в среднем

Распределяет элементы по корзинам, потом сортирует каждую.

Когда использовать: числа с равномерным распределением, floating-point числа.

Таблица сравнения

Практический совет

В Python используй встроенный sorted() или list.sort(). Они используют Timsort — гибрид Merge Sort и Insertion Sort.

O(n log n) гарантировано, очень оптимизирован для реальных данных.

Выводы

Не существует сравнительной сортировки быстрее O(n log n).

Но есть алгоритмы, которые:

• Гарантируют O(n log n): Merge Sort, Heapsort, Introsort
• Обходят O(n log n) для специальных типов: Counting, Radix, Bucket Sort
• На практике быстрее Quicksort: Introsort, Timsort

Для общего случая используй встроенные функции сортировки!