Optimized N-deque partition dual-deque merge string sorting algorithm

String sorting is a fundamental operation in various data-intensive applications, ranging from bioinformatics to database indexing. However, parallelizing string sorting remains challenging due to irregular memory access patterns, which often lead to inefficient cache utilization. This paper introduces the Parallel N-Deque Partition Dual-Deque Merge string sorting algorithm, which is evaluated against several state-of-the-art parallel sorting techniques. It utilizes a parallel block-based partitioning strategy to divide the data into smaller blocks for independent sorting. The algorithm harnesses the N-Deque data structure and OpenMP scheduling to optimize execution efficiency. The performance is evaluated on two distinct platforms: an Apple M2 (8-core) and an Intel Xeon Gold 6142 (16-core). Experimental results demonstrate that speedups of 5.25 × and 11.92 × can be obtained on the Apple M2 and Intel Xeon Gold 6142, respectively. Moreover, parallel efficiencies of 0.65 and 0.74 are achieved when sorting 20 and 50 million random strings, respectively. Factors such as input data size, block size, sorting cutoff, OpenMP scheduling types, and the number of deques significantly impact runtime performance by influencing cache misses and branch mispredictions.