O(n log n) — linearithmic complexity

This is the optimal complexity for most sorting algorithms. You can't consistently sort faster than O(n log n) unless you know something specific about the input data.

Example: 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);
}

Recursion splits the array in half down to the base case (one or two elements), and then merges them back in the right order. This approach achieves O(n log n) complexity — because log n is the depth of the recursion, and n is merging all the elements at each level.

← Previous: O(log n) — logarithmic complexity · Whole series · Next: O(n²) — quadratic complexity →

First published in Ukrainian in the Telegram channel “Created to die” on June 23, 2025.