← O(n log n) — linearithmic complexity
docs: English JsonRpcBundle docs, REST and MCP Bundle sections, package cards
en/articles/from-tg/series/algorithm-complexity/o-n-log-n.md
new file +37
−0
1
+
# O(n log n) — linearithmic complexity
2
+
3
+
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.
4
+
5
+
## Example: merge sort
6
+
7
+
```php
8
+
function mergeSort($array) {
9
+
if (count($array) <= 1) return $array;
10
+
11
+
$middle = floor(count($array) / 2);
12
+
$left = mergeSort(array_slice($array, 0, $middle));
13
+
$right = mergeSort(array_slice($array, $middle));
14
+
15
+
return merge($left, $right);
16
+
}
17
+
18
+
function merge($left, $right) {
19
+
$result = [];
20
+
while (count($left) && count($right)) {
21
+
$result[] = $left[0] < $right[0] ? array_shift($left) : array_shift($right);
22
+
}
23
+
return array_merge($result, $left, $right);
24
+
}
25
+
```
26
+
27
+
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.
28
+
29
+
:::tip
30
+
If you see recursion + merging / combining / iteration — it's almost always O(n log n).
31
+
:::
32
+
33
+
← [Previous: O(log n) — logarithmic complexity](/articles/from-tg/series/algorithm-complexity/o-log-n) · [Whole series](/articles/from-tg/series/algorithm-complexity) · [Next: O(n²) — quadratic complexity →](/articles/from-tg/series/algorithm-complexity/o-n2)
34
+
35
+
---
36
+
37
+
*First published in Ukrainian in the Telegram channel [“Created to die”](https://t.me/php_while_true/37) on June 23, 2025.*