This repo holds the notes and code I made when researching parallelism and implementating tests for the new High Performance Computing environment at Kean University.
Generally, sorting algorithms have gotten extremely efficient to the point of O(nlogn). The experiments just explore some last grasps at squeezing out some micro-efficiencies, of which it fails. However, it proves a great learning exercise for understanding and implementing multi-threaded design because of the inherent divide-and-conquer design of already efficient sorting algorithms. The algorithms explored extensively were merge-sort and quick-sort as well as a modified version of quick sort with two pivot positions reffered to as dual-pivot-quick-sort. I also speculate on quick-sort with more than two pivots up to n and the diminishing returns and possible step backwards it causes.
The implementation explores allocating each recurssive call a new thread as well as dividing the initial list to all available threads and then combinging the threads after each finishes it's work.
In addition to this I researched papers that have looked into this subject prior and examine an already optimized parallel sorting algorithm design by the folk at Oracle that is included in the Java standard library. Here is a visualization of the benchmarks:
