O(n log n) — лінійно-логарифмічна складність

Це оптимальна складність для більшості алгоритмів сортування. Ви не зможете стабільно сортувати швидше, ніж O(n log n), якщо не знаєте чогось специфічного про вхідні дані.

Приклад: сортування злиттям (Merge Sort)

function mergeSort($array) {
    if (count($array) <= 1) return $array;

    $middle = floor(count($array) / 2);
    $left = mergeSort(array_slice($array, 0, $middle));
    $right = mergeSort(array_slice($array, $middle));

    return merge($left, $right);
}

function merge($left, $right) {
    $result = [];
    while (count($left) && count($right)) {
        $result[] = $left[0] < $right[0] ? array_shift($left) : array_shift($right);
    }
    return array_merge($result, $left, $right);
}

Рекурсія ділить масив навпіл до базового випадку (елемент або два), після чого їх зливає у правильному порядку. Цей підхід дозволяє досягти складності O(n log n) — бо log n — це глибина рекурсії, а n — злиття всіх елементів на кожному рівні.

← Попередня: O(log n) — логарифмічна складність · Уся серія · Наступна: O(n²) — квадратична складність →

Вперше опубліковано в Telegram-каналі «Створений щоб помирати» 23.06.2025.