автор
Стоит ли разбивать этот массив на части и сортировать по более мелким кускам (например по 16Кб - сортируем quickSort) а затем использовать сортировку слиянием? Либо особого выигрыша здесь уже не получить, т.к. данные уже в памяти.



Если сортировать в одном потоке, то не будет вообще никакого выигрыша. Однако если распараллелить сортировку частей, а потом сливать, то ускорение будет (если компьютер с многоядерным процессором или хотя бы процессор с hyperthreading). Однако думаю части должны быть крупными, иначе потребуется много слияний. Например, если процессор 2-ядерный, то разбиваем на 2 части и делаем 1 слияние. Даёт хороший прирост скорости, но с большой оговоркой - если время сортировки частей примерно одинаково, а оно зависит от распределения данных внутри части (это я проводил эксперименты). Для борьбы с этим можно поделить массив на большее число частей, но понадобится больше слияний, то есть их тоже желательно распараллелить по потокам. Порядок слияний влияет на их общую трудоёмкость.
Вообще-то уже есть функции сортировки, распараллеленные внутри себя по этому способу - в библиотеке GCC 4.4 есть распараллеленные варианты функций std::sort, std::stable_sort и др. для C++, да и не только в GCC.
Кстати, сейчас в стандартный библиотеках компиляторов обычно применяется алгоритм не QuickSort, а IntroSort, но для него справедливы те же выводы.

Gluk (Kazan)хреново он параллелится, между нами девочками

Вообще-то я уже ответил. Можно конечно уточнять. Но раз другие не уточняют, то сам это делаю.

Алоритм QuickSort распараллеливается хорошо, хотя бы потому,что его формулировка рекурсивная. Но самостоятельная эффективная реализация алгоритма нетривиальна, и нет самысла ею заниматься, можно применить функции сортировки из стандартных библиотек - причём есть как распараллеленные внутри (тогда самому ничего делать не надо), либо взять обычную не распалаллеленную версию и распараллелить самостоятельно. Для этого массив поделить на части, сортировать их параллельно и сливать. При этом возникают проблемы оптимизации, которые я уже описал.

Также, как я написал, в нынешних стандарных библиотеках вместо QuickSort обычно используется IntroSort - эта замена сделана для борьбы со "сложным случаем" сортировки в QuickSort, когда её трудоёмкость достигает O(N*N), хотя в среднем она O (N*LOG N). Таким образом, для самостоятельного программирования QuickSort надо разбираться в предмете, но особого смыла оно не имеет. (Для примера, в MS Visual Studio 2008, в библиотеке C++ функции qsort, std::sort и std::stable_sort все реализуют алгоритм IntroSort, ими и пользоваться. Сливать части - функцией std::merge - но это только в C++).

На сколько частей разбивать.
Независимо от числа частей, в среднем трудоёмкость сортировки составит O(N*LOG N). Но это не значит, что число частей не имеет значения. Потому что надо учесть факторы:
- число частей при распараллеливании должно быть не меньше числа потоков выполнения (зависит от числа процессоров, ядер и наличия hyperthreading). Наапример, 2 ядра без hyperthreading - делаем не менее 2 потоков.
- но если сделать ровно 2 (как в описанном случае), а распределение значений не случайное, то один поток может закончить работу быстрее, чем второй, и простивать. Поэтому сделать больше - скажем, десяток. Одновременно пусть работают 2 и если один отсортирует свой отрезок, пусть начинает сортировать ещё не сортированный или сливать уже отсортированные. Очень много отрезков делать ни к чему, т.к. оптимизация от равномерной загрузки ядер будет уже небольшая.
- Порядок слияния отсортированных частей влияет на трудоёмкость слияния.
- Можно попытаться сделать оптимизацию типа "суперлинейный рост скорости". А именно, обычно рост скорости от распараллеливания - медленнее роста числа процессоров (закон Амдаля), но иногда бывает и более быстрым, чем рост числа процессоров (ядер). Это происходит, когда сортируемая часть массива полностью помещается в кеш, относящийся к процееору (ядру). То есть, ориентировочно сотни килобайт. Более мелкие куски массива уже нет смысла делать. Подробнее о "суперлинейном росте скорости" можно ппочитать в документации по организации многопоточной обработки OpenMP, но он - не свойство OpenMP, а свойство архитектуры компьютера. Библиотека OpenMP вообще удобна для распараллеливания сортировки, хотя совершенно необязательна.

Вот, написал сколько хватило терпения. Напоследок привожу фрагменты моёй программы сортировки с распараллеливанием на 2 потока функции std::stable_sort (которую легко заменить на любую другую), применяется библиотека OpenMP. Полные примеры для Visual C++ и GCC я уже привёл на форуме ixbt. Пример примитивный - в явном виде задаются 2 потока, для демонстрации идеи. Библиотека OpenMP позволяет легко задавать число потоков динамически (что и следовало бы сделать в практической программе). Но демонстрация возможностей OpenMP не являлась задачей.

Пример. Определение массива (можно заменить на любое другое):

Сортирующий фрагмент кода:

На дурацкие комментарии отвечать не буду. Нет ничего настолько простого, чтобы не нашёлся кто-нибудь, неспособный это понять. В общем, я описал распараллеливание сортировки довольно подробно. Может, кому-нибудь поможет. А если кому не поможет, то пусть это будет его проблемой.

Да, по OpenMP можно найти книжки на английском языке и много статей.