Рассмотрим подробнее алгоритм сортировки слиянием. Его основная идея состоит в том, что массив разбивается на части, они сортируются отдельно, а затем, упорядоченные части сливаются. При наличии процедуры слияния алгоритм может быть выполнен рекурсивно следующим образом:

1. массив разбивается на две половины;

2. каждая половинка сортируется;

3. упорядоченные половины сливаются.

Для эффективного распараллеливания данного алгоритма необходимо найти части, обладающие наибольшей вычислительной нагрузкой и не зависящие друг от друга. В этом смысле алгоритм очень удобен для распараллеливания, так как подразумевает деление массива на независимые части, их независимую друг от друга сортировку, и последующее объединение.

Исходя из вышесказанного, параллельный алгоритм делит исходный массив на p равных частей по количеству процессов, каждый процесс выполняет сортировку слиянием своей части, отсортированные части массива отсылаются на основной поток (данном случае нулевой), на котором происходит их слияние.