Linux 下多線程排序的實現

對於計算密集型的任務，如果能采用合理的多線程處理，能夠大大的提升計算效率。這篇博文實現了多線程排序，同時講解了一些需要注意的問題。

首先，說一下總體的思路：將元素分成n段，使用快速排序多個線程並行處理。最後需要等待這些線程都將分段排好序之後，進行類似歸並排序的過程。

這樣時間復雜度算下來是(假設我是４核的機器)　O(n+n/4log(n/4))，比O(nlogn)大概快了一倍的樣子。（請帶入數值具體計算）

先來介紹一下pthread_barrier系列函數。

函數原型：
#include 
int pthread_barrier_init(pthread_barrier_t *restrict barrier, const pthread_barrierattr_t *restrict attr, unsigned count);
int pthread_barrier_wait(pthread_barrier_t *barrier);
int pthread_barrier_destroy(pthread_barrier_t *barrier);

參數解釋：

pthread_barrier_t，是一個計數鎖，對該鎖的操作都包含在三個函數內部，我們不用關心也無法直接操作。只需要實例化一個對象丟給它就好。

pthread_barrierattr_t，鎖的屬性設置，設為NULL讓函數使用默認屬性即可。

count，你要指定的等待個數。

通俗解釋:

pthread_barrier_*其實只做且只能做一件事，就是充當欄桿（barrier意為欄桿)。形象的說就是把先後到達的多個線程擋在同一欄桿前，直到所有線程到齊，然後撤下欄桿同時放行。1）init函數負責指定要等待的線程個數；2） wait()函數由每個線程主動調用，它告訴欄桿“我到起跑線前了”。wait(）執行末尾欄桿會檢查是否所有人都到欄桿前了，如果是，欄桿就消失所有線程繼續執行下一句代碼；如果不是，則所有已到wait()的線程停在該函數不動，剩下沒執行到wait()的線程繼續執行；3）destroy函數釋放init申請的資源。

單線程排序：

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

//錯誤檢查函數
inline void ERR_EXIT(const string &msg,int retnum)
{
    if(retnum!=0)
    {
        cerr<