Пытаюсь сделать мультипоточную быструю сортировку. Основная загвоздка вот в чем:
Допустим, на вход поступает массив: 2, 6, 8, 4, 0, 3, 7, 4. Одному потоку достаются элементы [0..3] другому [4..7]. На выходе от потоков получаем два отсортированных массива: 2, 4, 6, 8 и 0, 3, 4, 7. Ну а здесь получается нужно еще как-то эти два массива слить (фактически заново отсортировать), что нарушает условие задачи.

В общем у меня ощущение, что я выбрал в принципе не верный путь решения  
По идее потоки должны сортировать не свои кусочки массива, а работать как бы сообща над всем массивом сразу. 
Есть идеи, как это можно правильно перейти от рекурсивного алгоритма к мультипоточному?

заново сортировать не надо, вам осталось получать минимальные элементы из двух очередей

Lipetsk, я немного не уточнил - число потоков не обязательно равно 2, может быть и больше (этот параметр задается) => подмассивов будет больше. 

PS. Я уже нашел способ объединить в порядке возрастания два массива, остается решить, как объединять большее число. Если я конечно вообще на правильном пути    

метод quicksort предполагает несколько другую последовательность действий:
сначала мы разделяем массив на две части так, что любое число из первой части меньше любого числа из второй части, поэтому сразу после сортировки этих частей массив получается отсортированным
как вариант, для двух потоков можно первое разделение провести в однопоточном режиме, а уже отдельные части сортировать в разных потоках

Первый проход будет в однопоточном режиме, массив отсортируется относительно среднего элемента. Потом запускаем по потоку на правую и левую часть, и так рекурсивно, то есть один поток после упорядочивания создает два дочерних потока и завершается. Можно ввести ограничение на количество одновременно выполняемых потоков.

Вот что у меня получилось.



В общем схема такая, как расписал Silent. 


Все вроде правильно - верно сортируется массив, работает заданное число потоков. Но вот что я не пойму - почему при чистой рекурсии (если MaxThreads=0) массив сортируется  быстрее (загружая на 50% процессор), хотя 2 поточная версия использует каждое ядро и грузит проц на 100%...

Вот данные замеров (число элементов = 10`000`000):
Число спец. потоков для сортировки  / время в миллисек.
0 / 13000
2 / 15203
4 / 49250

Вот такая картина. По идее на моем 2-ядерном процессоре, должна быстрее работать версия, которая используется на всю два ядра. Но почему-то выигрывает чисто рекурсивная версия...

Есть мысли? 

после разделения работы между потоками никаких блокировок в рабочих циклах быть не должно.

Действительно! У нас ведь уже определены границы массива внутри одного потока и они не могут нарушиться. Закомментировал крит. секцию cs - теперь действительно поточная версия сортирует где-то на 1.3 сек. быстрее чисто рекурсивной. Да и вообще появился общий выигрыш во времени.

Еще думаю оптимизировать один кусок, путем создания массива хендлов потоков и функции WaitForMultipleObjects(). Возможно она не так будет грузить проц, как вот эта проверка:

кроме того, стоит подумать о накладных расходах
конечно, если мы создаём поток для того, чтобы отсортировать 10000000 элементов, скорее всего, станет быстрее
однако, для 10элементов я бы ужене был так уверен

создание потока - нетривиальное действие, которое затрагивуает обращение к системе, создание там каких-то структур и т.д.

так что его стоит минимизировать:
1. нет смысла создавать поток для сортировки маленьких кусочков массивов
2. возможно, стоит поразмыслить на пулом потоков - создать и вначале в количестве, например, равном количеству доступных ядер, а потом делать что-то типа набора текущих задач, из которых выбирать следующую длякаждого освободившегося потока

maxim1000, насчет маленьких кусочков - в точку. Нужно будет экспериментально подобрать эту границу.