Care este complexitatea algoritmului de sortare prin îmbinare în cel mai rău caz?

Сложность алгоритма сортировки слиянием (merge sort) в худшем случае составляет O(n log n), где n — количество элементов в сортируемом массиве.

Объяснение:

• Алгоритм рекурсивно делит массив пополам, что происходит примерно log n раз.
• На каждом уровне рекурсии происходит слияние двух отсортированных половин, что требует O(n) операций.

Таким образом, общее время работы — произведение количества уровней рекурсии на время слияния на каждом уровне: O(n) * O(log n) = O(n log n).