glenggg / fastparallelmergesort Goto Github PK
View Code? Open in Web Editor NEWOpenMP parallelized merge sort optimized with merge sort algorithm (for the record, this seems to be the only version available on github that implemented merge sort algorithm with OpenMP). Traditional parallel merge sort cannot efficiently parallel merge process. With merge path algorithm, we can achieve O(n/d) time complexity (traditional parallel merge sort can only achieve O(n) during the last few merge steps) on merge process. More detail about merge sort algorithm can be found: https://arxiv.org/abs/1406.2628 .