PPQSort: Pattern Parallel Quicksort
摘要
This paper presents PPQSort (Pattern Parallel Quicksort), a new parallel quicksort algorithm that provides high performance and ease of use. PPQSort uses C++ threads for parallelization, achieving efficient sorting without external libraries and allowing seamless integration across different computing environments. This paper describes novel quicksort optimizations, including branchless partitioning and their efficient parallel implementation. PPQSort is compared with existing parallel quicksort algorithms on different machines and with different input data. Experimental evaluation results demonstrate that PPQSort is fast and robust, consistently outperforming the fastest available parallel quicksort implementations for almost all inputs.