22. Алгоритм «разделяй и властвуй». Условия достижения оценки nlogn.

Упорядочивание массива.

Разбиваем массив до состояния отдельных элементов-они будут упорядоченными массивами затем используем алгоритм «слияние»

Задача упорядочивания n чисел решается за O(nlogn)(logn-количество слоев) с помощью метода слияния массивов.

Допустим есть два упорядоченных массива чисел, тогда сравниваем два первых числа из каждого массива и меньшее переносим в результат. Затем повторяем сравнения до того, как массивы не будут пусты(«слияние») Оценка О(n) трудоемкость на каждом слое.

Таким образом, для сортировки неупорядоченного массива его нужно разделить на пары чисел, которые упорядочиваются по вышеописанному алгоритму. Затем из полученных упорядоченных пар формируются новые пары, которые обрабатываются по тому же алгоритму и так далее.