Изменения

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

Как видно из оценки первого алгоритма, слияние является его узким местом. Попытаемся распараллелить слияние, для чего рассмотрим алгоритм рекурсивного слияния массивов <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_{3}]</tex>:

# Убедимся, что размер <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">T[right_{1} \dots mid_{1} - 1]</tex> и <tex dpi="120">T[right_{2} \dots mid_{2}]</tex> в <tex dpi="120">A[right_{3} \dots mid_{3} - 1]</tex>

# Сольем <tex dpi="120">T[mid_{1} + 1 \dots right_{1}]</tex> и <tex dpi="120">T[mid_{2} \dots right_{2}]</tex> в <tex dpi="120">A[mid_{3} + 1 \dots right_{3}]</tex>

===Реализация===