Изменения

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

Несмотря на наличие двух рекурсивных вызовов, при оценке будем считать, что совершается один вызов, т.к. оба вызова выполняются параллельно с одинаковой асимптотикой. Оценим время работы данного алгоритма: <mathtex>T(n) = T(n / 2) + \Theta(n) = \Theta(n)</mathtex>. Данная асимптотика достигается при возможности запускать неограниченное количество потоков независимо друг от друга.<br>

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

// если <mathtex>right \leqslant left</mathtex> возвращает <mathtex>left</mathtex> // если <mathtex>x \leqslant T[left]</mathtex>, возвращает <mathtex>left</mathtex> // иначе возвращает наибольший индекс <mathtex>i</mathtex> из отрезка <mathtex>[left; right]</mathtex> такой, что <mathtex>array[i - 1] < x</mathtex>

// слияние <mathtex>T[left_{1} \dots right_{1}]</mathtex> и <mathtex>T[left_{2} \dots right_{2}]</mathtex> в <mathtex>A[left_{3} \dots right_{1} - left_{1} + right_{2} - left_{2}]</mathtex> mergeMT(T, left<mathtex>_{1}</mathtex>, right<mathtex>_{1}</mathtex>, left<mathtex>_{2}</mathtex>, right<mathtex>_{2}</mathtex>, A, left<mathtex>_{3}</mathtex>): n<mathtex>_{1}</mathtex> = right<mathtex>_{1}</mathtex> - left<mathtex>_{1}</mathtex> + 1 n<mathtex>_{2}</mathtex> = right<mathtex>_{2}</mathtex> - left<mathtex>_{2}</mathtex> + 1 '''if ''' n<mathtex>_{1}</mathtex> < n<mathtex>_{2}</mathtex>: swap(left<mathtex>_{1}</mathtex>, left<mathtex>_{2}</mathtex>) swap(right<mathtex>_{1}</mathtex>, right<mathtex>_{2}</mathtex>) swap(n<mathtex>_{1}</mathtex>, n<mathtex>_{2}</mathtex>)

'''if ''' n<mathtex>_{1}</mathtex> == 0: '''return''' '''else''' mid<mathtex>_{1}</mathtex> = (left<mathtex>_{1}</mathtex> + right<mathtex>_{1}</mathtex>) / 2 mid<mathtex>_{2}</mathtex> = binarySearch(T[mid<mathtex>_{1}</mathtex>], T, left<mathtex>_{2}</mathtex>, right<mathtex>_{2}</mathtex>) mid<mathtex>_{3}</mathtex> = left<mathtex>_{3}</mathtex> + (mid<mathtex>_{1}</mathtex> - left<mathtex>_{1}</mathtex>) + (mid<mathtex>_{2}</mathtex> - left<mathtex>_{2}</mathtex>) A[mid<mathtex>_{3}</mathtex>] = T[mid<mathtex>_{1}</mathtex>] '''spawn''' mergeMT(T, left<mathtex>_{1}</mathtex>, mid<mathtex>_{1}</mathtex> - 1, left<mathtex>_{2}</mathtex>, mid<mathtex>_{2}</mathtex> - 1, A, left<mathtex>_{3}</mathtex>) mergeMT(T, mid<mathtex>_{1}</mathtex> + 1, right<mathtex>_{1}</mathtex>, mid<mathtex>_{2}</mathtex>, right<mathtex>_{2}</mathtex>, A, mid<mathtex>_{3}</mathtex> + 1)

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

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

'''if ''' n == 1:

'''else''' создадим новый массив T[1 <mathtex>\dots</mathtex> n]

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

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