146
правок
Изменения
Нет описания правки
# Убедимся, что размер <tex dpi="120">T[left_{1} \dots right_{1}]</tex> больше либо равен размеру <tex dpi="120">T[left_{2} \dots right_{2}]</tex>
# Возьмем <tex dpi="120">x = T[mid_{1}]</tex> - — середину первого массива (<tex dpi="120">x</tex> также является и медианой этого массива)
# При помощи [[Целочисленный двоичный поиск|бинарного поиска]] найдем <tex dpi="120">mid_{2}</tex> такое, что <tex dpi="120">\forall y \in T[left_{2} \dots mid_{2} - 1]: y < x</tex>
# <tex dpi="120">mid_{3} = left_{3} + (mid_{1} - left_{1}) + (mid_{2} - left_{2})</tex>
===Реализация===
<font color=green>// если <tex dpi="120"color=green>right \leqslant left</tex> возвращает <tex dpi="120">left</tex>
// если <tex dpi="120">x \leqslant T[left]</tex>, возвращает <tex dpi="120">left</tex>
// иначе возвращает наибольший индекс <tex dpi="120">i</tex> из отрезка <tex dpi="120">[left, right]</tex> такой, что <tex dpi="120">array[i - 1] < x</tex></font>
'''integer''' binarySearch(x, array, left, right)
<font color=green>// слияние <tex dpi="120">T[left_{1} \dots right_{1}]</tex> и <tex dpi="120">T[left_{2} \dots right_{2}]</tex> в <tex dpi="120">A[left_{3} \dots right_{1} - left_{1} + right_{2} - left_{2}]</tex></font>
'''function''' mergeMT(T, left<tex dpi="120">_{1}</tex>, right<tex dpi="120">_{1}</tex>, left<tex dpi="120">_{2}</tex>, right<tex dpi="120">_{2}</tex>, A, left<tex dpi="120">_{3}</tex>):
n<tex dpi="120">_{1}</tex> = right<tex dpi="120">_{1}</tex> - left<tex dpi="120">_{1}</tex> + 1
<tex dpi="135">n_{2} = 2 \cdot \frac{n_{2}}{2} \leqslant \frac{(n_{1} + n_{2})}{2} = \frac{n}{2}</tex>.<br>
В худшем случае один из двух рекурсивных вызовов сольет <tex dpi="135">\frac{n_{1}}{2}</tex> элементов <tex dpi="120">T[left_{1} \dots right_{1}]</tex> с <tex dpi="120">n_{2}</tex> элементами <tex dpi="120">T[left_{2} \dots right_{2}]</tex> и тогда количество элементов первых двух массивов в рекурсивном вызове будет равно<br>
<tex dpi="135">\frac{n_{1}}{2} + n_{2} \leqslant \frac{n_{1}}{2} + \frac{n_{2}}{2} + \frac{n_{2}}{2} = \frac{(n_{1} + n_{2})}{2} + \frac{n_{2}}{2} \leqslant \frac{n}{2} + \frac{n}{4} = \frac{3}{4}n</tex>.<br>Асимптотика каждого вызова функции - — <tex dpi="120">\Theta(\log n)</tex>, т.е. время, затрачиваемое на бинарный поиск. Так как рекурсивные вызовы функции выполняются параллельно, а потоки при оценке независимы, время их выполнения будет равно времени выполнения самого долгого вызова. В худшем случае это <tex dpi="120">T(\frac{3}{4}n)</tex>. Тогда получим оценку сверху<br><tex dpi="130">T_{\mathrm {merge}}(n) = T_{\mathrm {merge}}(\frac{3}{4}n) + \Theta(\log n) = \Theta(\log^2 n)</tex>
==Сортировка с многопоточным слиянием==
Очевидно, что нижняя оценка алгоритма сортировки с многопоточным слиянием выше. Таким образом, при приведенных выше допущениях алгоритм сортировки с однопоточным слиянием эффективнее и его асимптотика составляет <tex dpi="120">\Theta(\frac{n}{N_{ind}}\log \frac{n}{N_{ind}})</tex>.
==См. также==
*[[Сортировка слиянием]]
*[[PSRS-сортировка]]
==Источники информации==
*Cormen T.H., Leiserson C.E., Rivest R.L., Stein C. {{---}} Introduction to Algorithms, Third Edition
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: СортировкаСортировки]]
