Implementation of multithreaded sorting under Linux

For computationally intensive tasks, if you can use reasonable multithreading, you can greatly improve your computational efficiency. This blog post implements multi-threaded sorting and explains some issues that need attention.

First, let's talk about the general idea: divide the element into n segments, and use the quick-sort multiple threads to process in parallel. Finally, we need to wait for these threads to sort the segments, and then perform a process similar to the merge sort.

This time complexity is calculated (assuming I am a 4-core machine) O(n+n/4log(n/4)), which is about twice as fast as O(nlogn). (Please bring in the numerical calculation)

Let me introduce the pthread_barrier series of functions.

Function prototype: #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 is a count lock. The operation of the lock is contained in three functions. We don't care or operate directly. Just instantiate an object and throw it at it. 
 
 pthread_barrierattr_t, the property setting of the lock, set to NULL to let the function use the default property. 
 
 count, the number of waits you want to specify. 
 
 Popular explanation: 
 pthread_barrier_* actually only does one thing and only acts as a railing (barrier means railing). The image is to block multiple threads that have arrived in the same railing until all the threads are in line, then remove the railing and release. 1) The init function is responsible for specifying the number of threads to wait; 2) the wait() function is called by each thread actively, it tells the railing "I am before the starting line". Wait() executes the end railing to check if everyone is in front of the railing. If it is, the railing disappears and all threads continue to execute the next code; if not, all threads that have reached wait() stop at this function. The remaining threads that have not executed to wait() continue to execute; 3) the destroy function releases the resources requested by init. 
 Single-threaded sorting: 
 
#include #include #include #include #include #include #include #include #include #include using namespace std;//Error checking function inline void ERR_EXIT(const string & Msg,int retnum){ if(retnum!=0) { cerr<