并行化快速排序设想

并行化快速排序

对于一般的快速排序，总是使用分治法将任务划分成两个子任务。那么，子任务之间是相互对立的。不仅如此，它不像归并排序的分治之后还需要汇总的过程。

因此，可以相当然，将一趟快排与任务联系起来。

规定：QuickSort(arr, l, r) 为一趟快排。
由于任务之间两两独立，每趟快排完成之后(即确认了一个数的下标后),我们可以将子任务并行执行，化为两个段范围的子任务，对于个数比较少的任务，我们可以使用插入算法直接处理。

因为是计算密集型的程序，为了最大化性能，我们直接设计线程池重用线程。

void  QuickSort(arr, beg, end){
    if(end - beg <= 5) {
        inserted_sort(arr, beg, end);
        return;
    }
    
    mid = beg + (end - beg)/2;
    pool.addTask(QuickSort(arr, beg, mid));
    pool.addTask(QuickSort(arr, mid, end));
}

其实，跟递归版本的快排没什么区别

关于同步方面，只要使用一个定制版本的CountDownLatch，主线程wait, 每投递一个任务就计数自增，在函数结束的时刻再down,防止过早的down导致提前唤醒主线程。

void  QuickSort(arr, beg, end){
    
    if(end - beg <= 5) {
        inserted_sort(arr, beg, end);
        return;
    }
    
    mid = beg + (end - beg)/2;
    pool.addTask(QuickSort(arr, beg, mid));
    pool.addTask(QuickSort(arr, mid, end));
    
    latch.inc(2); // count = count + 2; 
    latch.down(); // count = count - 1;
}

主线程的部分

threadpool pool;

CountDownLatch latch;

latch.inc(1);

pool.addTask(QuickSort(arr, beg, end))

latch.wait();

关于并行化归并排序

对于归并排序的并行化，与快排也差不多。只不过需要在结束两个子任务时候，进行同步。性能方面，应该没有快速排序的快。因为，任务线程之间同步，导致我们不能很好地重用线程。当然，我们可以用类似于协程的手段去解决这种阻塞问题。