Parallelized Quick Sort Ideas

Parallelized Quicksort

For general quicksort, always divide the task into two subtasks using divide and conquer.Then, the subtasks are opposed to each other.Not only that, it is not like the merge sort process that needs to be aggregated after the divide and conquer.

Therefore, it's natural to associate a quicksort trip with a mission.

Specification: QuickSort(arr, l, r) is a quick sort.
Since the tasks are independent of each other, after each quicksort is completed (that is, after confirming the subscript of a number), we can execute the subtasks in parallel and turn them into two subtasks in the range of segments.Less tasks, we can use the insertion algorithm to handle directly.

Because it is a computationally intensive program, in order to maximize performance, we directly design a thread pool to reuse threads.

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));}

Actually, it's no different from the recursive version of Quicksort

About synchronization, as long as a customized version of CountDownLatch is used, the main thread waits, and the count increases every time a task is delivered, and then goes down at the end of the function to prevent premature down from causing the main thread to wake up early.

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;}

Part of the main thread

threadpool pool;CountDownLatch latch;latch.inc(1);pool.addTask(QuickSort(arr, beg, end))latch.wait();

About Parallelizing Merge Sort

The parallelization of merge sort is similar to quicksort.It just needs to be synchronized when the two subtasks are ended.In terms of performance, it should not be as fast as quicksort.Because of synchronization between task threads, we can't reuse threads well.Of course, we can solve this blocking problem with methods similar to coroutines.