3.Сортировка слиянием

1.Делим массив на 2 части

2.Рекурсивно сортируем каждую часть

3.Объединяем обе части так, чтобы получить отсортированный массив

Трудоемкость - O(nlogn)

Теорема. Не существует алгоритма сортировки со

сложностью меньшей, чем C*nlogn.

Сложность задачи – это сложность лучшего алгоритма

для ее решения.

Теорема. Сложность задачи сортировки - nlogn