Как это правильно реализовать. Я вот беру массив делю на попалам. Первую часть отдаю одному потоку, вторую другому. А потом финальная сортировка вставкой. Это так делается?
Делить пополам а потом сливать - не очень хорошая идея, т.к. общее время будет равняться худшему из потоков. И если для 2,3,4 потоков разница между средним и худшим будет не столь существенна, то при массовом параллелизме простои будут очень большими.
А почему простои. Потоки блокироваться не будут т.к. каждый поток работает со своим куском данных. И в сортировке шелла не надо выполнять последний этап - сортировка вставками. Это сделается в самом конце одним потоком. Сравню результаты сколько времени в одном потоке, а сколько с несколькими потоками.
