Algorithm Improvement of Two-Way Merge Sort Based on OpenMP
Jun Zhang, Yong Ping Gao, Yue Shun He, Xue Yuan Wang · Applied Mechanics and Materials · 2014
Two-way merge sort algorithm has a good time efficiency which has been used widely. The sort algorithm can be improved on speed and efficient based on its own potential parallelism via the parallel processing capacity of multi-core processor and the convenient programming interface of OpenMP. The time complexity is improved to O(nlog2n/TNUM) and inversely proportional to the number of parallel threads. The experiment results show that the improved two-way merge sort algorithm become much more efficient compared to the traditional one.