C++11引入了多线程库（前身Boost线程库），借助future 异步线程机制可以非常方面的实现一个多线程版本的快排序，std::async可以自动选择是创建线程时执行还是调用get的线程中执行（避免过度订阅）。
这里的实现方法，对传入的链表是毁灭性的，排序结束，旧的无序链表将为空。
#include <iostream>
#include <list>
#include <random>
#include <future>
#include <algorithm>
template <typename T>
std::list<T> fast_sort(std::list<T> &input)
{
if(input.empty())
return input;
std::list<T> ret;
const T pivot = *(input.begin());
auto div = std::partition(input.begin(),input.end(),[&pivot](const T t){return t<pivot;});
ret.push_back(*div);
std::list<T> high;
high.splice(high.begin(),input,input.begin(),div);
input.pop_front();
std::list<T> low(std::move(input));
std::future<std::list<T>> run = std::async(fast_sort<T>,std::ref(high));
auto ret_high=run.get();
auto ret_low=fast_sort(low);
ret.splice(ret.begin(),ret_high);
ret.splice(ret.end(),ret_low);
return ret;
}
int main(){
std::list<int> test;
std::random_device gen;
for(int i=0;i<1000;i++)
test.push_back(gen()%100);
for(auto & x: test)
std::cout<<x<<std::endl;
std::cout<<"-----------"<<std::endl;
auto test_x = fast_sort<int>(test);
for(auto & x: test_x)
std::cout<<x<<std::endl;
return 0;
}
