感谢网友浅水清流投递本稿。
并发算法是多核时代开始流行的技术趋势，比如tbb，ppl都提供了大量有用的并发算法。
经典算法中，排序是一个很适合采用分治法并发的场合，比如快速排序。
常规的快速排序，先在数组中选取一个基准点，将数组分区为小于基准点和大于基准点（相同的数可以到任一边），对分区的子数组递归的执行分区的操作，当子数组长度为1时退出递归。此时数组就完成了排序过程。
01 int partition(int* array, int left, int right) 02{ 03 int index = left; 04 int pivot = array[index]; 05 swap(array[index], array[right]); 06 for (int i=left; i<right; i++) 07 { 08 if (array[i] > pivot) // 降序 09 swap(array[index++], array[i]); 10 } 11 swap(array[right], array[index]); 12 return index; 13} 14 15 void qsort(int* array, int left, int right) 16{ 17 if (left >= right) 18 return; 19 int index = partition(array, left, right); 20 qsort(array, left, index - 1); 21 qsort(array, index + 1, right); 22}对快排的过程分析可以发现，分区以及对子数组排序的过程均可以并发执行，这里首先对数组进行分区，生成分区数组，为了保证不同分区不受到影响需要先完成分区再进行排序。
01 template <typename key, typename container >void parallel_sort(container & _container)template <typename key, typename container > 02 void partition_less(std::vector<key> * vless, container * _container, key privot){ 03 for(size_t i = 0; i < (*_container).size(); i++){ 04 if ((*_container)[i] < privot){ 05 vless->push_back((*_container)[i]); 06 } 07 } 08} 09 10 template <typename key, typename container > 11 void partition_more(std::vector<key> * vmore, container * _container, key privot){ 12 for(size_t i = 0; i < (*_container).size(); i++){ 13 if ((*_container)[i] >= privot){ 14 vmore->push_back((*_container)[i]); 15 } 16 } 17}在完成分区之后，递归执行排序操作，并将排序好的分区重新写入待排序数组。
01 template <typename key, typename container > 02 int sort_less(container * _container, std::vector<key> & vless, boost::atomic_uint32_t * depth){ 03 parallel_sort_impl<key>(&vless, *depth); 04 05 for(size_t i = 0; i < vless.size(); i++){ 06 (*_container)[i] = vless[i]; 07 } 08 09 return 0; 10} 11 12 template <typename key, typename container > 13 int sort_more(container * _container, std::vector<key> & vmore, boost::atomic_uint32_t * depth){ 14 parallel_sort_impl<key>(&vmore, *depth); 15 16 size_t pos = (*_container).size()-vmore.size(); 17 for(size_t i = 0; i < vmore.size(); i++){ 18 (*_container)[i+pos] = vmore[i]; 19 } 20 21 return 0; 22} 23 24 template <typename key, typename container > 25 void parallel_sort_impl(container * _container, boost::atomic_uint32_t & depth){ 26 if (_container->size() < threshold || depth.load() > processors_count()){ 27 std::sort(_container->begin(), _container->end()); 28 }else{ 29 key privot = (*_container)[_container->size()/2]; 30 31 std::vector<key> vless, vmore; 32 auto partition_result = std::async(std::launch::async, partition_less<key, container>, &vless, _container, privot); 33 partition_more(&vmore, _container, privot); 34 partition_result.get(); 35 36 auto result = std::async(std::launch::async, sort_less<key, container>, _container, vless, &depth); 37 sort_more(_container, vmore, &depth); 38 result.get(); 39 } 40}这里采取了一个有趣的策略，就是通过数组的大小，计算出排序好的元素在原数组中的位置（这样即使是并发的访问数组，但是因为不同的线程各自访问的自己的下标位置，所以仍然是线程安全的），然后将排序好的数组直接写入到原数组，完成整个排序。
这里的并发采用了c++11中的promise:http://imcc.blogbus.com/logs/174131661.html
文章转自 并发编程网-ifeve.com
相关资源：整理最全资料：并行计算大作业：矩阵乘法，排序算法，代码 课件 报告超详细