Обсуждение участника:AKhimulya — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м
Строка 1: Строка 1:
 
== Многопоточная сортировка слиянием ==
 
== Многопоточная сортировка слиянием ==
Благодаря тому, что сортировка слиянием построена на принципе "Разделяй и властвуй", выполнение данного алгоритма можно весьма эффективно распараллелить. При оценке асимптотики допускается, что возможен запуск неограниченного количества независимых процессов, что на практике не достижимо. Более того, при реализации имеет смысл ограничить количество параллельных потоков.
+
Благодаря тому, что сортировка слиянием построена на принципе "Разделяй и властвуй", выполнение данного алгоритма можно весьма эффективно распараллелить. При оценке асимптотики допускается, что возможен запуск неограниченного количества независимых процессов, т.е. процессов с вычислительными ресурсами, не зависящими от других процессов, что на практике не достижимо. Более того, при реализации имеет смысл ограничить количество параллельных потоков.
 
===Сортировка с однопоточным слиянием===
 
===Сортировка с однопоточным слиянием===
 
Внесем в алгоритм сортировки слиянием следующую модификацию: будем сортировать левую и правую части массива параллельно.
 
Внесем в алгоритм сортировки слиянием следующую модификацию: будем сортировать левую и правую части массива параллельно.
Строка 14: Строка 14:
  
 
В данном алгоритме оператор '''spawn''' запускает новый поток, а оператор '''sync''' ожидает завершения этого потока. Функция merge аналогична функции merge из раздела [http://neerc.ifmo.ru/wiki/index.php?title=%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D1%81%D0%BB%D0%B8%D1%8F%D0%BD%D0%B8%D0%B5%D0%BC#.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>
 
В данном алгоритме оператор '''spawn''' запускает новый поток, а оператор '''sync''' ожидает завершения этого потока. Функция merge аналогична функции merge из раздела [http://neerc.ifmo.ru/wiki/index.php?title=%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D1%81%D0%BB%D0%B8%D1%8F%D0%BD%D0%B8%D0%B5%D0%BC#.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>
Несмотря на наличие двух рекурсивных вызовов, при оценке будем считать, что совершается один вызов, т.к. оба вызова выполняются параллельно с одинаковой асимптотикой. Оценим время работы данного алгоритма:  <math>T(n) = T(n / 2) + \Theta(n) = \Theta(n)</math>. Данная асимптотика достигается при возможности запускать неограниченное количество потоков независимо друг от друга.<br>
+
Несмотря на наличие двух рекурсивных вызовов, при оценке будем считать, что совершается один вызов, т.к. оба вызова выполняются параллельно с одинаковой асимптотикой. Оценим время работы данного алгоритма:  <tex>T(n) = T(n / 2) + \Theta(n) = \Theta(n)</tex>. Данная асимптотика достигается при возможности запускать неограниченное количество потоков независимо друг от друга.<br>
  
 
===Многопоточное слияние===
 
===Многопоточное слияние===
Как видно из оценки первого алгоритма, слияние выполняется слишком долго при том, что существует возможность его ускорить. Рассмотрим алгоритм рекурсивного слияния массивов <math>T[left_{1} \dots right_{1}]</math> и <math>T[left_{2} \dots right_{2}]</math> в массив <math>A[left_{3} \dots right_{3}]</math>:
+
Как видно из оценки первого алгоритма, слияние является его узким местом. Попытаемся распараллелить слияние, для чего рассмотрим алгоритм рекурсивного слияния массивов <tex>T[left_{1} \dots right_{1}]</tex> и <tex>T[left_{2} \dots right_{2}]</tex> в массив <tex>A[left_{3} \dots right_{3}]</tex>:
# Убедимся, что размер <math>T[left_{1} \dots right_{1}]</math> больше либо равен размеру <math>T[left_{2} \dots right_{2}]</math>
+
# Убедимся, что размер <tex>T[left_{1} \dots right_{1}]</tex> больше либо равен размеру <tex>T[left_{2} \dots right_{2}]</tex>
# Вычислим <math>x = T[mid_{1}]</math> - середину первого массива (<math>x</math> также является и медианой этого массива)
+
# Возьмем <tex>x = T[mid_{1}]</tex> - середину первого массива (<tex>x</tex> также является и медианой этого массива)
# При помощи бинарного поиска найдем <math>mid_{2}</math> такое, что <math>\forall y \in T[left_{2} \dots mid_{2} - 1]: y < x</math>
+
# При помощи бинарного поиска найдем <tex>mid_{2}</tex> такое, что <tex>\forall y \in T[left_{2} \dots mid_{2} - 1]: y < x</tex>
# <math>mid_{3} = left_{3} + (mid_{1} - left_{1}) + (mid_{2} - left_{2})</math>
+
# <tex>mid_{3} = left_{3} + (mid_{1} - left_{1}) + (mid_{2} - left_{2})</tex>
# <math>A[mid_{3}] = x</math>
+
# <tex>A[mid_{3}] = x</tex>
# Сольем <math>T[right_{1} \dots mid_{1} - 1]</math> и <math>T[right_{2} \dots mid_{2}]</math> в <math>A[right_{3} \dots mid_{3} - 1]</math>
+
# Сольем <tex>T[right_{1} \dots mid_{1} - 1]</tex> и <tex>T[right_{2} \dots mid_{2}]</tex> в <tex>A[right_{3} \dots mid_{3} - 1]</tex>
# Сольем <math>T[mid_{1} + 1 \dots right_{1}]</math> и <math>T[mid_{2} \dots right_{2}]</math> в <math>A[mid_{3} + 1 \dots right_{3}]</math>
+
# Сольем <tex>T[mid_{1} + 1 \dots right_{1}]</tex> и <tex>T[mid_{2} \dots right_{2}]</tex> в <tex>A[mid_{3} + 1 \dots right_{3}]</tex>
 
Рассмотрим псевдокод данного алгоритма:
 
Рассмотрим псевдокод данного алгоритма:
  
     // если <math>right \leqslant left</math> возвращает <math>left</math>
+
     // если <tex>right \leqslant left</tex> возвращает <tex>left</tex>
     // если <math>x \leqslant T[left]</math>, возвращает <math>left</math>
+
     // если <tex>x \leqslant T[left]</tex>, возвращает <tex>left</tex>
     // иначе возвращает наибольший индекс <math>i</math> из отрезка <math>[left; right]</math> такой, что <math>array[i - 1] < x</math>
+
     // иначе возвращает наибольший индекс <tex>i</tex> из отрезка <tex>[left; right]</tex> такой, что <tex>array[i - 1] < x</tex>
 
     binarySearch(x, array, left, right)
 
     binarySearch(x, array, left, right)
 
      
 
      
     // слияние <math>T[left_{1} \dots right_{1}]</math> и <math>T[left_{2} \dots right_{2}]</math> в <math>A[left_{3} \dots right_{1} - left_{1} + right_{2} - left_{2}]</math>
+
     // слияние <tex>T[left_{1} \dots right_{1}]</tex> и <tex>T[left_{2} \dots right_{2}]</tex> в <tex>A[left_{3} \dots right_{1} - left_{1} + right_{2} - left_{2}]</tex>
     mergeMT(T, left<math>_{1}</math>, right<math>_{1}</math>, left<math>_{2}</math>, right<math>_{2}</math>, A, left<math>_{3}</math>):
+
     mergeMT(T, left<tex>_{1}</tex>, right<tex>_{1}</tex>, left<tex>_{2}</tex>, right<tex>_{2}</tex>, A, left<tex>_{3}</tex>):
     n<math>_{1}</math> = right<math>_{1}</math> - left<math>_{1}</math> + 1
+
     n<tex>_{1}</tex> = right<tex>_{1}</tex> - left<tex>_{1}</tex> + 1
     n<math>_{2}</math> = right<math>_{2}</math> - left<math>_{2}</math> + 1
+
     n<tex>_{2}</tex> = right<tex>_{2}</tex> - left<tex>_{2}</tex> + 1
     if n<math>_{1}</math> < n<math>_{2}</math>:
+
     '''if''' n<tex>_{1}</tex> < n<tex>_{2}</tex>:
         swap(left<math>_{1}</math>, left<math>_{2}</math>)
+
         swap(left<tex>_{1}</tex>, left<tex>_{2}</tex>)
         swap(right<math>_{1}</math>, right<math>_{2}</math>)
+
         swap(right<tex>_{1}</tex>, right<tex>_{2}</tex>)
         swap(n<math>_{1}</math>, n<math>_{2}</math>)
+
         swap(n<tex>_{1}</tex>, n<tex>_{2}</tex>)
 
      
 
      
     if n<math>_{1}</math> == 0:
+
     '''if''' n<tex>_{1}</tex> == 0:
         return
+
         '''return'''
     else
+
     '''else'''
         mid<math>_{1}</math> = (left<math>_{1}</math> + right<math>_{1}</math>) / 2
+
         mid<tex>_{1}</tex> = (left<tex>_{1}</tex> + right<tex>_{1}</tex>) / 2
         mid<math>_{2}</math> = binarySearch(T[mid<math>_{1}</math>], T, left<math>_{2}</math>, right<math>_{2}</math>)
+
         mid<tex>_{2}</tex> = binarySearch(T[mid<tex>_{1}</tex>], T, left<tex>_{2}</tex>, right<tex>_{2}</tex>)
         mid<math>_{3}</math> = left<math>_{3}</math> + (mid<math>_{1}</math> - left<math>_{1}</math>) + (mid<math>_{2}</math> - left<math>_{2}</math>)
+
         mid<tex>_{3}</tex> = left<tex>_{3}</tex> + (mid<tex>_{1}</tex> - left<tex>_{1}</tex>) + (mid<tex>_{2}</tex> - left<tex>_{2}</tex>)
         A[mid<math>_{3}</math>] = T[mid<math>_{1}</math>]
+
         A[mid<tex>_{3}</tex>] = T[mid<tex>_{1}</tex>]
         '''spawn''' mergeMT(T, left<math>_{1}</math>, mid<math>_{1}</math> - 1, left<math>_{2}</math>, mid<math>_{2}</math> - 1, A, left<math>_{3}</math>)
+
         '''spawn''' mergeMT(T, left<tex>_{1}</tex>, mid<tex>_{1}</tex> - 1, left<tex>_{2}</tex>, mid<tex>_{2}</tex> - 1, A, left<tex>_{3}</tex>)
         mergeMT(T, mid<math>_{1}</math> + 1, right<math>_{1}</math>, mid<math>_{2}</math>, right<math>_{2}</math>, A, mid<math>_{3}</math> + 1)
+
         mergeMT(T, mid<tex>_{1}</tex> + 1, right<tex>_{1}</tex>, mid<tex>_{2}</tex>, right<tex>_{2}</tex>, A, mid<tex>_{3}</tex> + 1)
 
         '''sync'''
 
         '''sync'''
  
Оценим время выполнения данного алгоритма сверху при возможности запускать неограниченное количество потоков независимо друг от друга. Оба массива содержат <math>n_{1} + n_{2} = n</math> элементов. К моменту рекурсивных вызовов <math>n_{2} \leqslant n_{1}</math>, значит, <math>n_{2} = 2 * n_{2} / 2 \leqslant (n_{1} + n_{2}) / 2 = n / 2</math>. В худшем случае один из двух рекурсивных вызовов сольет <math>n_{1} / 2</math> элементов <math>T[left_{1} \dots right_{1}]</math> с <math>n_{2}</math> элементами <math>T[left_{2} \dots right_{2}]</math> и тогда количество элементов первых двух массивов в рекурсивном вызове будет равно <math>n_{1} / 2 + n_{2} \leqslant n_{1} / 2 + n_{2} / 2 + n_{2} / 2 = (n_{1} + n_{2}) / 2 + n_{2} / 2 \leqslant n / 2 + n / 4 = 3 * n / 4</math>. Так как рекурсивные вызовы функции выполняются параллельно, время их выполнения будет равно времени выполнения самого долгого вызова. В худшем случае это <math>T(3 * n / 4)</math>. Тогда суммарное время работы алгоритма слияния будет равно <math>Tmerge(n) = Tmerge(3 * n  / 4) + \Theta(\log(n)) = \Theta(\log^2(n))</math>, т.к. асимптотика каждого вызова функции - <math>\Theta(\log(n))</math>, т.е. время, затрачиваемое на бинарный поиск.
+
Оба массива содержат <tex>n_{1} + n_{2} = n</tex> элементов. К моменту рекурсивных вызовов <tex>n_{2} \leqslant n_{1}</tex>, значит,<br><tex>n_{2} = 2 \cdot n_{2} / 2 \leqslant (n_{1} + n_{2}) / 2 = n / 2</tex>.<br> В худшем случае один из двух рекурсивных вызовов сольет <tex>n_{1} / 2</tex> элементов <tex>T[left_{1} \dots right_{1}]</tex> с <tex>n_{2}</tex> элементами <tex>T[left_{2} \dots right_{2}]</tex> и тогда количество элементов первых двух массивов в рекурсивном вызове будет равно<br><tex>n_{1} / 2 + n_{2} \leqslant n_{1} / 2 + n_{2} / 2 + n_{2} / 2 = (n_{1} + n_{2}) / 2 + n_{2} / 2 \leqslant n / 2 + n / 4 = 3 \cdot n / 4</tex>.<br>Асимптотика каждого вызова функции - <tex>\Theta(\log(n))</tex>, т.е. время, затрачиваемое на бинарный поиск. Так как рекурсивные вызовы функции выполняются параллельно, а потоки при оценке независимы, время их выполнения будет равно времени выполнения самого долгого вызова. В худшем случае это <tex>T(3 \cdot n / 4)</tex>. Тогда получим оценку сверху<br><tex>T_{merge}(n) = T_{merge}(3 \cdot n  / 4) + \Theta(\log(n)) = \Theta(\log^2(n))</tex>
  
 
===Сортировка с многопоточным слиянием===
 
===Сортировка с многопоточным слиянием===
Приведем псевдокод алгоритма, использующего слияние из предыдущего раздела, сортирующего элементы <math>A[leftA \dots rightA]</math> и помещающего отсортированный массив в <math>B[leftB \dots leftB + rightA - leftA]</math>
+
Приведем псевдокод алгоритма, использующего слияние из предыдущего раздела, сортирующего элементы <tex>A[leftA \dots rightA]</tex> и помещающего отсортированный массив в <tex>B[leftB \dots leftB + rightA - leftA]</tex>
  
 
     mergeSortMT2(A, leftA, rightA, B, leftB):
 
     mergeSortMT2(A, leftA, rightA, B, leftB):
 
         n = r - p + 1
 
         n = r - p + 1
         if n == 1:
+
         '''if''' n == 1:
 
             B[leftB] = A[leftA]
 
             B[leftB] = A[leftA]
         else
+
         '''else'''
             создадим новый массив T[1 <math>\dots</math> n]
+
             создадим новый массив T[1 <tex>\dots</tex> n]
 
             mid = (leftA + rightA) / 2
 
             mid = (leftA + rightA) / 2
 
             newMid = mid - leftA + 1
 
             newMid = mid - leftA + 1
Строка 70: Строка 70:
 
             mergeMT(T, 1, newMid, newMid + 1, n, B, leftB)
 
             mergeMT(T, 1, newMid, newMid + 1, n, B, leftB)
  
Оценим данный алгоритм сверху при условии, что возможен запуск неограниченного количества независимых потоков. Из предыдущих пунктов <math>TmergeSort(n) = TmergeSort(n / 2) + Tmerge(n) = TmergeSort(n / 2) + \Theta(\log^2(n)) = \Theta(\log^3(n))</math>.
+
Оценим данный алгоритм сверху при условии, что возможен запуск неограниченного количества независимых потоков. Из предыдущих пунктов <tex>T_{mergeSort}(n) = T_{mergeSort}(n / 2) + T_{merge}(n) = T_{mergeSort}(n / 2) + \Theta(\log^2(n)) = \Theta(\log^3(n))</tex>.
  
 +
===Реализация===
 +
Очевидно, что при отсутствии возможности запуска неограниченного количества независимых потоков, вычислительная сложность многопоточного алгоритма зависит от максимально возможного количества независимых потоков. Обозначим такое количество как <tex>N_{ind}</tex>. Оценим приведенные выше алгоритмы с учетом наложенных ограничений:<br>
 +
::'''Сортировка с однопоточным слиянием''' будет иметь асимптотику <tex>\Theta(n/N_{ind}\log(n/N_{ind}) + n)</tex>:
 +
::::<tex>\Theta(n/N_{ind}\log(n/N_{ind}))</tex> операций нужно на последовательную сортировку массива длиной <tex>n/N_{ind}</tex>.
 +
::::<tex>\Theta(n)</tex> необходимо на последовательное слияние.
 +
::Соответветственно, асимптотика может быть как <tex>\Theta(n/N_{ind}\log(n/N_{ind}))</tex>, так и <tex>\Theta(n)</tex> в зависимости от <tex>N_{ind}</tex> и <tex>n</tex>
 +
::'''Многопоточное слияние''' будет работать за <tex>\Theta((\frac{n}{N_{ind}})^{(\log_{\frac{4}{3}}2)} + \log(n) \cdot min(N_{ind}, \log(n))</tex>
 +
::::Прежде чем достигнуть ограничения на создание нового потока, алгоритм углубится на <tex>min(N_{ind}, \log(n))</tex> уровней вглубь дерева рекурсии, где на каждом уровне выполняется бинпоиск за <tex>\Theta(\log(n))</tex>
 +
::::Асимптотика многопоточного слияния при работе в одном потоке по основной теореме рекуррентных соотношений равна
 +
::::<tex>T_{merge}'(n) = 2T_{merge}'(\frac {3}{4}n) + \Theta(\log(n)) = \Theta(n^{(\log_{\frac{4}{3}}2)})</tex>
 
===Литература===
 
===Литература===
Cormen T.H., Leiserson C.E., Rivest R.L., Stein C. - Introduction to Algorithms, Third Edition
+
Cormen T.H., Leiserson C.E., Rivest R.L., Stein C. {{---}} Introduction to Algorithms, Third Edition

Версия 06:22, 4 июня 2014

Многопоточная сортировка слиянием

Благодаря тому, что сортировка слиянием построена на принципе "Разделяй и властвуй", выполнение данного алгоритма можно весьма эффективно распараллелить. При оценке асимптотики допускается, что возможен запуск неограниченного количества независимых процессов, т.е. процессов с вычислительными ресурсами, не зависящими от других процессов, что на практике не достижимо. Более того, при реализации имеет смысл ограничить количество параллельных потоков.

Сортировка с однопоточным слиянием

Внесем в алгоритм сортировки слиянием следующую модификацию: будем сортировать левую и правую части массива параллельно.

   mergeSortMT(array, left, right):
       mid = (left + right) / 2
   
       spawn mergeSortMT(array, left, mid)
       mergeSortMT(array, mid + 1, right)
       sync
   
       merge(array, left, mid, right)

В данном алгоритме оператор spawn запускает новый поток, а оператор sync ожидает завершения этого потока. Функция merge аналогична функции merge из раздела слияние двух массивов.
Несмотря на наличие двух рекурсивных вызовов, при оценке будем считать, что совершается один вызов, т.к. оба вызова выполняются параллельно с одинаковой асимптотикой. Оценим время работы данного алгоритма: [math]T(n) = T(n / 2) + \Theta(n) = \Theta(n)[/math]. Данная асимптотика достигается при возможности запускать неограниченное количество потоков независимо друг от друга.

Многопоточное слияние

Как видно из оценки первого алгоритма, слияние является его узким местом. Попытаемся распараллелить слияние, для чего рассмотрим алгоритм рекурсивного слияния массивов [math]T[left_{1} \dots right_{1}][/math] и [math]T[left_{2} \dots right_{2}][/math] в массив [math]A[left_{3} \dots right_{3}][/math]:

  1. Убедимся, что размер [math]T[left_{1} \dots right_{1}][/math] больше либо равен размеру [math]T[left_{2} \dots right_{2}][/math]
  2. Возьмем [math]x = T[mid_{1}][/math] - середину первого массива ([math]x[/math] также является и медианой этого массива)
  3. При помощи бинарного поиска найдем [math]mid_{2}[/math] такое, что [math]\forall y \in T[left_{2} \dots mid_{2} - 1]: y \lt x[/math]
  4. [math]mid_{3} = left_{3} + (mid_{1} - left_{1}) + (mid_{2} - left_{2})[/math]
  5. [math]A[mid_{3}] = x[/math]
  6. Сольем [math]T[right_{1} \dots mid_{1} - 1][/math] и [math]T[right_{2} \dots mid_{2}][/math] в [math]A[right_{3} \dots mid_{3} - 1][/math]
  7. Сольем [math]T[mid_{1} + 1 \dots right_{1}][/math] и [math]T[mid_{2} \dots right_{2}][/math] в [math]A[mid_{3} + 1 \dots right_{3}][/math]

Рассмотрим псевдокод данного алгоритма:

   // если [math]right \leqslant left[/math] возвращает [math]left[/math]
   // если [math]x \leqslant T[left][/math], возвращает [math]left[/math]
   // иначе возвращает наибольший индекс [math]i[/math] из отрезка [math][left; right][/math] такой, что [math]array[i - 1] \lt  x[/math]
   binarySearch(x, array, left, right)
   
   // слияние [math]T[left_{1} \dots right_{1}][/math] и [math]T[left_{2} \dots right_{2}][/math] в [math]A[left_{3} \dots right_{1} - left_{1} + right_{2} - left_{2}][/math]
   mergeMT(T, left[math]_{1}[/math], right[math]_{1}[/math], left[math]_{2}[/math], right[math]_{2}[/math], A, left[math]_{3}[/math]):
   n[math]_{1}[/math] = right[math]_{1}[/math] - left[math]_{1}[/math] + 1
   n[math]_{2}[/math] = right[math]_{2}[/math] - left[math]_{2}[/math] + 1
   if n[math]_{1}[/math] < n[math]_{2}[/math]:
       swap(left[math]_{1}[/math], left[math]_{2}[/math])
       swap(right[math]_{1}[/math], right[math]_{2}[/math])
       swap(n[math]_{1}[/math], n[math]_{2}[/math])
   
   if n[math]_{1}[/math] == 0:
       return
   else
       mid[math]_{1}[/math] = (left[math]_{1}[/math] + right[math]_{1}[/math]) / 2
       mid[math]_{2}[/math] = binarySearch(T[mid[math]_{1}[/math]], T, left[math]_{2}[/math], right[math]_{2}[/math])
       mid[math]_{3}[/math] = left[math]_{3}[/math] + (mid[math]_{1}[/math] - left[math]_{1}[/math]) + (mid[math]_{2}[/math] - left[math]_{2}[/math])
       A[mid[math]_{3}[/math]] = T[mid[math]_{1}[/math]]
       spawn mergeMT(T, left[math]_{1}[/math], mid[math]_{1}[/math] - 1, left[math]_{2}[/math], mid[math]_{2}[/math] - 1, A, left[math]_{3}[/math])
       mergeMT(T, mid[math]_{1}[/math] + 1, right[math]_{1}[/math], mid[math]_{2}[/math], right[math]_{2}[/math], A, mid[math]_{3}[/math] + 1)
       sync

Оба массива содержат [math]n_{1} + n_{2} = n[/math] элементов. К моменту рекурсивных вызовов [math]n_{2} \leqslant n_{1}[/math], значит,
[math]n_{2} = 2 \cdot n_{2} / 2 \leqslant (n_{1} + n_{2}) / 2 = n / 2[/math].
В худшем случае один из двух рекурсивных вызовов сольет [math]n_{1} / 2[/math] элементов [math]T[left_{1} \dots right_{1}][/math] с [math]n_{2}[/math] элементами [math]T[left_{2} \dots right_{2}][/math] и тогда количество элементов первых двух массивов в рекурсивном вызове будет равно
[math]n_{1} / 2 + n_{2} \leqslant n_{1} / 2 + n_{2} / 2 + n_{2} / 2 = (n_{1} + n_{2}) / 2 + n_{2} / 2 \leqslant n / 2 + n / 4 = 3 \cdot n / 4[/math].
Асимптотика каждого вызова функции - [math]\Theta(\log(n))[/math], т.е. время, затрачиваемое на бинарный поиск. Так как рекурсивные вызовы функции выполняются параллельно, а потоки при оценке независимы, время их выполнения будет равно времени выполнения самого долгого вызова. В худшем случае это [math]T(3 \cdot n / 4)[/math]. Тогда получим оценку сверху
[math]T_{merge}(n) = T_{merge}(3 \cdot n / 4) + \Theta(\log(n)) = \Theta(\log^2(n))[/math]

Сортировка с многопоточным слиянием

Приведем псевдокод алгоритма, использующего слияние из предыдущего раздела, сортирующего элементы [math]A[leftA \dots rightA][/math] и помещающего отсортированный массив в [math]B[leftB \dots leftB + rightA - leftA][/math]

   mergeSortMT2(A, leftA, rightA, B, leftB):
       n = r - p + 1
       if n == 1:
           B[leftB] = A[leftA]
       else
           создадим новый массив T[1 [math]\dots[/math] n]
           mid = (leftA + rightA) / 2
           newMid = mid - leftA + 1
           spawn mergeSortMT2(A, leftA, mid, T, 1)
           mergeSortMT2(A, mid + 1, rightA, T, newMid + 1)
           sync
           mergeMT(T, 1, newMid, newMid + 1, n, B, leftB)

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

Реализация

Очевидно, что при отсутствии возможности запуска неограниченного количества независимых потоков, вычислительная сложность многопоточного алгоритма зависит от максимально возможного количества независимых потоков. Обозначим такое количество как [math]N_{ind}[/math]. Оценим приведенные выше алгоритмы с учетом наложенных ограничений:

Сортировка с однопоточным слиянием будет иметь асимптотику [math]\Theta(n/N_{ind}\log(n/N_{ind}) + n)[/math]:
[math]\Theta(n/N_{ind}\log(n/N_{ind}))[/math] операций нужно на последовательную сортировку массива длиной [math]n/N_{ind}[/math].
[math]\Theta(n)[/math] необходимо на последовательное слияние.
Соответветственно, асимптотика может быть как [math]\Theta(n/N_{ind}\log(n/N_{ind}))[/math], так и [math]\Theta(n)[/math] в зависимости от [math]N_{ind}[/math] и [math]n[/math]
Многопоточное слияние будет работать за [math]\Theta((\frac{n}{N_{ind}})^{(\log_{\frac{4}{3}}2)} + \log(n) \cdot min(N_{ind}, \log(n))[/math]
Прежде чем достигнуть ограничения на создание нового потока, алгоритм углубится на [math]min(N_{ind}, \log(n))[/math] уровней вглубь дерева рекурсии, где на каждом уровне выполняется бинпоиск за [math]\Theta(\log(n))[/math]
Асимптотика многопоточного слияния при работе в одном потоке по основной теореме рекуррентных соотношений равна
[math]T_{merge}'(n) = 2T_{merge}'(\frac {3}{4}n) + \Theta(\log(n)) = \Theta(n^{(\log_{\frac{4}{3}}2)})[/math]

Литература

Cormen T.H., Leiserson C.E., Rivest R.L., Stein C. — Introduction to Algorithms, Third Edition