Алгоритм сортировки, работающий в худшем, в среднем и в лучшем случае (то есть гарантированно) за O(n log n) операций при сортировке n элементов. Количество применяемой служебной памяти не зависит от размера массива (то есть, O(1)).
| Лучшая | Средняя | Худшая |
|---|---|---|
| n log n | n log n | n log n |