A Parallel Quicksort Algorithm Based on Partition and Merge Operations

JIA Siyu

doi:10.3969/j.issn.1672-9722.2019.10.012

Abstract：As an important operation in computer programming,sorting should be faster and more efficient under big data con?ditions. Along with the continual progress in the modern processor production technology,laptops,desktops,and commercial serv?ers are equipped with at least dual-core processors,and 4-core,8-core and 16-core processors are not rare any more. It is a 50% waste of the performance to run a single-thread program on a dual-core processor,as well as a 75% waste on a 4-core processor. The multiple program logic can be run simultaneously by the multithread multicore processors,and the advantage of multicore pro?cessors can be given actually,which achieves the purpose of making full use of processors. To improve the performance of sorting op?erations,the flexible parallel library OpenMP and the quicksort function qsort provided in the C/C++language standard library are adopted. A parallel quicksort algorithm on any shared-memory parallel computer is implemented. The experimental results show that under the same condition,taking the standard library serial quicksort function qsort as the benchmark,the performance of the 200M random integer data has been increased by 11.92 times under the eight-thread condition on the Intel Core i7-4790 processor platform. On the same data,that of Intel Core 2 Quad Q9400 processor has been improved by 4.75 times.