97
правок
Изменения
м
<tex>\mathrm {mergeSortMT}</tex>(array, left, right):
<tex>\mathrm {\bf {'''spawn}}</tex> <tex>\mathrm {''' mergeSortMT}</tex>(array, left, mid) <tex>\mathrm {mergeSortMT}</tex>(array, mid + 1, right) <tex>\mathrm {\bf {'''sync}}</tex>'''
<tex>\mathrm {merge}</tex>(array, left, mid, right)
<tex>\mathrm {binarySearch}</tex>(x, array, left, right)
<tex>\mathrm {mergeMT}</tex>(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>):
<tex>\mathrm {\bf {'''if}}</tex> ''' n<tex dpi="120">_{1}</tex> < n<tex dpi="120">_{2}</tex> <tex>\mathrm {swap}</tex>(left<tex dpi="120">_{1}</tex>, left<tex dpi="120">_{2}</tex>) <tex>\mathrm {swap}</tex>(right<tex dpi="120">_{1}</tex>, right<tex dpi="120">_{2}</tex>) <tex>\mathrm {swap}</tex>(n<tex dpi="120">_{1}</tex>, n<tex dpi="120">_{2}</tex>)
<tex>\mathrm {\bf {'''if}}</tex> ''' n<tex dpi="120">_{1}</tex> == 0 <tex>\mathrm {\bf {'''return}}</tex>''' <tex>\mathrm {\bf {'''else}}</tex>'''
<tex>\mathrm {\bf {'''spawn}}</tex> <tex>\mathrm {''' mergeMT}</tex>(T, left<tex dpi="120">_{1}</tex>, mid<tex dpi="120">_{1}</tex> - 1, left<tex dpi="120">_{2}</tex>, mid<tex dpi="120">_{2}</tex> - 1, A, left<tex dpi="120">_{3}</tex>) <tex>\mathrm {mergeMT}</tex>(T, mid<tex dpi="120">_{1}</tex> + 1, right<tex dpi="120">_{1}</tex>, mid<tex dpi="120">_{2}</tex>, right<tex dpi="120">_{2}</tex>, A, mid<tex dpi="120">_{3}</tex> + 1) <tex>\mathrm {\bf {'''sync}}</tex>'''
<tex>\mathrm {mergeSortMT2}</tex>(A, leftA, rightA, B, leftB):
<tex>\mathrm {\bf {'''if}}</tex> ''' n == 1
<tex>\mathrm {\bf {'''else}}</tex>'''
<tex>\mathrm {\bf {'''spawn}}</tex> <tex>\mathrm {''' mergeSortMT2}</tex>(A, leftA, mid, T, 1) <tex>\mathrm {mergeSortMT2}</tex>(A, mid + 1, rightA, T, newMid + 1) <tex>\mathrm {\bf {'''sync}}</tex>''' <tex>\mathrm {mergeMT}</tex>(T, 1, newMid, newMid + 1, n, B, leftB)
Нет описания правки
Внесем в алгоритм сортировки слиянием следующую модификацию: будем сортировать левую и правую части массива параллельно.
mid = (left + right) / 2
В данном алгоритме оператор <tex>\mathrm {\bf {spawn}}</tex> запускает новый поток, а оператор <tex>\mathrm {\bf {sync}}</tex> ожидает завершения этого потока. Функция <tex>\mathrm {merge}</tex> аналогична одноименной функции из раздела [[Сортировка слиянием#.D0.A1.D0.BB.D0.B8.D1.8F.D0.BD.D0.B8.D0.B5_.D0.B4.D0.B2.D1.83.D1.85_.D0.BC.D0.B0.D1.81.D1.81.D0.B8.D0.B2.D0.BE.D0.B2|слияние двух массивов]].<br>
// если <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>
// слияние <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>
n<tex dpi="120">_{1}</tex> = right<tex dpi="120">_{1}</tex> - left<tex dpi="120">_{1}</tex> + 1
n<tex dpi="120">_{2}</tex> = right<tex dpi="120">_{2}</tex> - left<tex dpi="120">_{2}</tex> + 1
mid<tex dpi="120">_{1}</tex> = (left<tex dpi="120">_{1}</tex> + right<tex dpi="120">_{1}</tex>) / 2
mid<tex dpi="120">_{2}</tex> = binarySearch(T[mid<tex dpi="120">_{1}</tex>], T, left<tex dpi="120">_{2}</tex>, right<tex dpi="120">_{2}</tex>)
mid<tex dpi="120">_{3}</tex> = left<tex dpi="120">_{3}</tex> + (mid<tex dpi="120">_{1}</tex> - left<tex dpi="120">_{1}</tex>) + (mid<tex dpi="120">_{2}</tex> - left<tex dpi="120">_{2}</tex>)
A[mid<tex dpi="120">_{3}</tex>] = T[mid<tex dpi="120">_{1}</tex>]
Оба массива содержат <tex dpi="120">n_{1} + n_{2} = n</tex> элементов. К моменту рекурсивных вызовов <tex dpi="120">n_{2} \leqslant n_{1}</tex>, значит,<br>
Приведем псевдокод алгоритма, использующего слияние из предыдущего раздела, сортирующего элементы <tex dpi="120">A[leftA \dots rightA]</tex> и помещающего отсортированный массив в <tex dpi="120">B[leftB \dots leftB + rightA - leftA]</tex>
n = r - p + 1
B[leftB] = A[leftA]
создадим новый массив T[1 <tex dpi="120">\dots</tex> n]
mid = (leftA + rightA) / 2
newMid = mid - leftA + 1
Оценим данный алгоритм сверху при условии, что возможен запуск неограниченного количества независимых потоков. Из предыдущих пунктов <tex dpi="130">T_{\mathrm {mergeSort}}(n) = T_{\mathrm {mergeSort}}(\frac{n}{2}) + T_{\mathrm {merge}}(n) = T_{\mathrm {mergeSort}}(\frac{n}{2}) + \Theta(\log^2 n) = \Theta(\log^3 n)</tex>.
