Сортировка слиянием относится к алгоритмам, работающим по принципу "разделяй и властвуй":
 сортируемый массив разбивается на части, для каждой части снова вызывается процедура сортировки, после чего происходит слияние отсортированных частей. Таким образом разбиение "углубляется" до тех пор, пока массив не оказывается разбитым на участки по два элемента, сортировкой которых и будет являться слияние. Затем в ходе обратного процесса - слияния всё более крупных частей - результирующий массив окажется упорядоченным по неубыванию.
Такое построение алгоритма даёт немалые возможности к его распараллеливанию - если выделить каждую процедуру слияния двух смежных блоков в отдельный поток, который будет выполняться на отдельном процессоре, операции слияния будут проводиться параллельно. Но создавать в результате по потоку на каждую пару элементов массива было бы невыгодно, поэтому применяется компромиссный вариант: массив разбивается на P блоков по числу процессоров, запускается P потоков последовательной сортировки отдельных блоков, после чего блоки сливаются. Процесс слияния блоков обычно не распареллеливают, но расчеты показали, что распараллеливание слияния блоков должно ускорять процесс финального слияния, причём эффективность распараллеленного слияния по сравнению с обычным будет возрастать с увеличеснием числа задействованных процессоров.
Также опытным путём было выяснено, что скорость последовательной сортировки сильно повышается при устранении из алгоритма рекурсии, что может быть объяснено отсутствием дополнительных затрат на многочисленные вызовы функций с передачей параметров, а также пересылку элементов из массива в буфер и обратно, так как метод буферизации был тоже несколько улучшен. Теперь, в улучшенном варианте алгоритма, массив сразу разбивается на элементарные блоки по 2 (1) элемента, которые потом попарно сливаются.

Исходный массив
4 1 2 8 5 9 5 3 3 2
Разбиение на блоки, сортируемые параллельно
Поток 1	Поток 2
4 1 2 8 5	9 5 3 3 2
Разбиение на элементарные массивы по 1-2 элемента	Разбиение на элементарные массивы по 1-2 элемента
4 1 2 8 5	9 5 3 3 2
Слияние внутри элементарных массивов	Слияние внутри элементарных массивов
1 4 2 8 5	5 9 3 3 2
Слияние	Слияние
1 2 4 8 5	3 3 5 9 2
Слияние	Слияние
1 2 4 5 8	2 3 3 5 9
Слияние блоков
1 2 2 3 3 4 5 5 8 9