Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
The runtime of Quicksort can be significantly reduced if multiple threads running on multiple cores can be used. With just two cores, just partition an array into two halves and let another thread sort the second half.
The problem is that with many cores, say eight, the initial partition of the array takes a very significant amount of time.
Does anyone have an idea how the partitioning of an array could be made faster if multiple cores running multiple threads are available?
Yes. Below is one idea that comes to me. Suppose for simplicity of description that you have 8 cores. There are three phases; the partitioning and sorting phases are the most expensive, and both can be parallelized.
Pivot selection phase: Select 7 pivots in any convenient fashion. For instance, randomly sample 128 items from the array, then use quickselect or quicksort on these 128 items to select the items ranked 16, 32, 48, 64, 80, 96, 112.
Partitioning phase: Divide the array into 8 equal-sized chunks. For instance, the first chunk contains the first 1/8th of the array, the second chunk contains the second 1/8th of the array, and so on. Each thread is responsible for one chunk. The thread's job is to partition its own chunk into 8 partitions, using the 7 pivots. At the end of the partitioning phase, we obtain 64 partitions.
Sorting phase: Each thread is responsible for 8 partitions, one from each chunk. It should coalesce those 8 partitions and then sort them. For instance, the first thread is responsible for coalescing and sorting the smallest partition from each chunk, the second thread is responsible for coalescing and sorting the second-smallest partition from each chunk, and so on.
Wikipedia describes some other schemes: https://en.wikipedia.org/wiki/Quicksort#Parallelization.
