Изменения

Оценим данный алгоритм сверху при условии, что возможен запуск неограниченного количества независимых потоков. Из предыдущих пунктов <tex>T_{mergeSort}(n) = T_{mergeSort}(\frac{n}{2}) + T_{merge}(n) = T_{mergeSort}(\frac{n}{2}) + \Theta(\log^2(n)) = \Theta(\log^3(n))</tex>.

Очевидно, что при отсутствии возможности запуска неограниченного количества независимых потоков, вычислительная сложность многопоточного алгоритма зависит от максимально возможного количества независимых потоков. Обозначим такое количество как <tex>N_{ind}</tex>. Допустим, <tex>n</tex> много больше <tex>N_{ind}</tex>, что в общем случае верно для ПК и достаточно больших объемов данных. Оценим приведенные выше алгоритмы с учетом наложенных ограничений и допущений:<br>

::[[#.D0.A1.D0.BE.D1.80.D1.82.D0.B8.D1.80.D0.BE.D0.B2.D0.BA.D0.B0_.D1.81_.D0.BE.D0.B4.D0.BD.D0.BE.D0.BF.D0.BE.D1.82.D0.BE.D1.87.D0.BD.D1.8B.D0.BC_.D1.81.D0.BB.D0.B8.D1.8F.D0.BD.D0.B8.D0.B5.D0.BC|Сортировка с однопоточным слиянием]] будет иметь асимптотику <tex>\Theta(\frac{n}{N_{ind}}\log(\frac{n}{N_{ind}}) + n) = \Theta(\frac{n}{N_{ind}}\log(\frac{n}{N_{ind}}))</tex>: