Parallel Block-InsertionSort

In this work, we design a parallel algorithm of the Block-InsertionSort (BiS) method by taking advantage of the high degree of parallelization that BiS offers, which performs multiple insertions of already sorted element blocks. As a result, we present a parallel implementation using OpenMP, evaluating its performance with different input sizes and data distributions. We also compared it against various parallel versions of classical sorting algorithms and state-of-the-art parallel sorting algorithms with available implementations. Our final version -which relies on multiway merge routines from libstdc++ parallel mode- was able to achieve significant performance improvements, close to 17 x average speedup on 32 cores.