Quick-merge sort algorithm based on Multi-core linux
Yong Mei Liu, Yan Zhu Yang · 2013
Sorting a list of input numbers is one of the most fundamental problems in the field of computer science. This paper presents an efficient implementation and detailed analysis of quick sort algorithm called QM-sort on Multi-core CPU architectures. Our QM-sort has two stages. The first stage is making blocks sorted, and the second stage is merging the sorted blocks. At the first stage, we propose a parallel quick sort algorithm named BPQsort. The run time of BPQsort achieves 40%-50% better than Qsort (STL), so we make blocks sorted more efficient. On the other hand, our algorithm can read file in parallel, thus reduce the time of reading file from disk. At the second stage, our parallel merge algorithm can operate the data on consecutive memory. Thus we avoid the expensive unaligned load/store operations, thus make our merge algorithm faster. At last, the run time of QM-sort is 10%-15% better than quick sort based on OpenMP.