Optimized N-deque partition dual-deque merge string sorting algorithm Authors: Sirilak Ketchaya, Apisit Rattanatranurak Published: 2026 ABSTRACT AbstractString 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.Keywords: Parallel algorithm, Sorting, String, OpenMPSubject terms: Engineering, Mathematics and computing, Physics Introduction Sorting is a crucial algorithm widely applied to solve problems in various fields such as biology, big data, engineering, and computer science. Several conventional sorting algorithms, such as QuickSort, MergeSort, and Radix Sort, have been extensively studied and parallelized to handle large-scale datasets. Quicksort is a widely recognized algorithm that employs the divide-and-conquer paradigm, relying on an efficient partitioning mechanism to sort data. This paradigm recursively partitions the dataset into smaller subproblems (divide) and sorts them once they reach a predefined cutoff (conquer). Typically, the process begins by partitioning the dataset into two disjoint subsets based on a selected pivot element. This step is performed recursively until the partitions reach a predefined cutoff, at which point the data within each partition is sorted using its sequential sorting algorithm. This work introduces the Parallel N-Deque Partition Dual-Deque Merge string sorting algorithm. By adopting a block-based partitioning scheme, the algorithm effectively minimizes synchronization overhead while maximizing parallel throughput. In this paper, a novel algorithm named Parallel N-Deque Partition Dual-Deque Merge String Sorting Algorithm, which utilizes a block-based partitioning concept to enhance sorting efficiency. The sequential partitioning is replaced with the parallel N-Deque Partitioning algorithm. However, this partitioning approach necessitates a subsequent merging phase to reintegrate the dispersed data. To achieve this, the Dual-Deque Merge algorithm is employed, effectively consolidating the sub-partitions into a single, correctly ordered sequence. The OpenMP library1 is utilized in this algorithm to parallelize the partitoning, and sorting algoirthm, enhancing its efficiency and performance. The performance of the algorithm is evaluated using the following metrics: run time, speedup, and efficiency. Subsequently, we optimized this algorithm by utilizing an N-Deque in the partitioning step, which significantly enhances its performance. In the previous work, we employed a parallel Multi-deque data structure for partitioning the data, but its number of threads was not controllable. Furthermore, OpenMP scheduling is implemented to optimize the partitioning phase. This feature enables dynamic workload distribution across threads, allowing for more granular control over parallel block execution. By effectively balancing the task load, this approach significantly enhances performance compared to our previous work. Finally, string sorting in this algorithm is implemented, which compares string data efficiently. The contributions of this paper are as follows: (1) The Parallel N-Deque Partition Dual-Deque Merge algorithm is proposed as a high-performance solution specifically designed for parallel string sorting. (2) Scheduling strategies are evaluated to optimize the partitioning phase and identify the most effective workload distribution for parallel execution. (3) The N-Deque data structure is incorporated into the partitioning process to demonstrate scalability and efficiency across various configurations. (4) A string sorting mechanism is integrated within the proposed algorithm. Background and related work In this section, the related works of the sequential and parallel sorting algorithms, OpenMP, and Dual-Deque Merge algorithm are presented. Related works Sorting is a fundamental algorithm that is widely implemented and available in the C++ Standard Template Library (STL). The std::sort function, provided through the header, is a highly optimized sorting utility used to arrange data in a specific order. Internally, std::sort utilizes the Introsort algorithm, which combines the efficiency of Quicksort and Heapsort during the divide phase. For smaller data in the conquer phase, it employs Insertion Sort to ensure optimal performance across a wide range of data sizes and patterns. In this paper, Parallel BQSort2 and MWSort are executed on our system as benchmark algorithms. BQSort employs a block-based parallel partitioning strategy, similar to the approach proposed by Tsigas and Zhang3. The data is divided into multiple blocks, which are partitioned concurrently. The remaining elements within each block are relocated to the center of the subarray, where a sequential partitioning algorithm is subsequently applied to finalize the distribution. On the other hand, parallel Multi-Way Merge sort (MWSort) is based on the merge sort paradigm. It initially divides the input data into smaller, equally sized segments, which are subsequently merged in parallel using a specialized parallel merge algorithm known as the Multi-way Merge algorithm. This method utilizes a temporary array to store the merged data, requiring at least twice the original memory. Intel Threading Building Blocks (TBB)4 provides a highly optimized implementation of parallel sorting, specifically through the function (TBBSort). It primarily employs the divide and conquer paradigm, utilizing a parallelized version of Quicksort or Introsort in some version. TBBSort partitions the data into two subarrays using a pivot. This partitioning algorithm is recursively run until the subarray becomes sufficiently small and sorts them sequentially. The efficiency of TBBSort is largely attributed to the TBB Work-Stealing Scheduler, using a local double-ended queue (deque). When a thread becomes idle, it attempts to steal a task from the tail of another thread. This ensures that all available CPU cores remain productive and increase CPU utilization. There are several studies that have explored the implementation of parallel sorting algorithms. In 1990, a parallel quicksort algorithm utilizing the Fetch-and-Add instruction was implemented on a Parallel Random-Access Machine (PRAM), achieving a speedup of 400 when sorting elements using 500 processors5. In 2008, Mishra et al.6 conducted an analysis and comparison of various sorting algorithms, including bubble sort, selection sort, insertion sort, merge sort, quicksort, and heap sort. Furthermore, the paper presented the time, space complexities, and stability of each algorithm. Ultimately, this paper demonstrated that the optimal sorting algorithm selection is contingent upon the data size, memory constraints, and the necessity of stability. This research serves as a valuable resource for comprehending the trade-offs inherent in different sorting strategies. Later, NG and Kakehi7 presented the LCP-MergeSort algorithm. The LCP concept is implemented to minimize character-wise comparisons and key accesses by leveraging the longest common prefixes (LCP) between the strings. Furthermore, there exists an implementation of parallel string radix sort8, which is a highly optimized implementation renowned for its exceptional cache efficiency and performance in string distribution. LCP-MergeSort enhances recursive merge sort by maintaining an average computational complexity of . In 2013, Tsigas and Zhang3 introduced PQuicksort, a block-based parallel sorting algorithm that partitions data concurrently and neutralizes the blocks. This method achieved a speedup of 11 on a 32-core processor. Bingmann et al.9 developed parallel K-way LCP-merge on NUMA architectures in 2017. Given their and K-way LCP-merge implementations, this constructs a fast parallel external memory string sorter for short strings. Its throughput is likely to exceed the available I/O bandwidth. Gebili et al. proposed the Parallel Multidimensional Lookahead Sorting algorithm, designed to run efficiently on General-Purpose Graphics Processing Units (GPUs)10. Subsequently, Cortis et al. introduced the Parallelised Modified Quickselect algorithm, which is conceptually similar to quicksort11. Marowka12 evaluated the performance of the parallel quicksort algorithm. Marowka’s work introduced a vector-based quicksort that integrates both process-based and thread-based execution models. In 2021, a parallel multi-deque sorting algorithm was proposed13, utilizing a block-based partitioning strategy. Each thread maintains its own deque to store the boundary indices of blocks. The algorithm performs partitioning by simultaneously traversing the array from both ends—left and right—toward the center. In 2022, the parallel sorting algorithm named In-place Parallel Super Scalar Samplesort (IPSo) was proposed14. The iHmas algorithm, which performs partitioning and sorting in parallel using MPI, was further optimized by Helal and Shaheen15 to enhance its performance. In addition, Mubarak et al.16 introduced preprocessing techniques that can be applied prior to sorting, significantly reducing time complexity. Later, the Dual Parallel Partition Sorting algorithm was introduced17, which partitions data using two threads during the initial stage. It incorporates the Multi-Swap algorithm for merging, achieving a speedup of up to 6.82 on a 4-core Intel i7-6770 processor. More recently, in 2023, a novel parallel sorting algorithm named Parallel MPDMSort was proposed18. It employs a block-based parallel partitioning approach, followed by the Dual-Deque Merge algorithm to efficiently merge the partitioned data. This method achieved a speedup of 13.81 on an Intel Xeon Gold 6142 processor. The performance of sorting algorithms has been significantly enhanced through various techniques and innovations. Gupta et al.19 proposed a GPU-based sorting algorithm leveraging a sorted matrix structure, achieving a fivefold speedup relative to the CUDA Thrust library20. Mankowitz et al.21 explored the use of deep reinforcement learning to improve sorting algorithm performance. Kobus et al.22 optimized segmented sorting on GPUs, achieving speedups ranging from 1.26 to 1.35 on four GPUs. Vásquez et al.23 proposed the Parallel Block-InsertionSort algorithm, also implemented using OpenMP. Each block is sorted independently, and a multiway merge algorithm from the libstdc++ parallel mode is used to combine the results. This approach yielded a speedup of up to 17 on a 32-core processor. Yang et al.24 developed thSort, a parallel bitonic sorting algorithm tailored for the FT-M7032 CPU-DSP heterogeneous processor, achieving a speedup of up to 2.15 compared to std::sort. Takase et al.25 presented the H-P Sort algorithm implemented on GPU, demonstrating a 3.45 speedup over its original version. Alhabboub et al.26 introduced a parallel large-scale quicksort algorithm using the OpenMP library, capable of sorting millions of elements in approximately 16,339 milliseconds. Dang’ana and Jacobsen27 presented FractalSort, a novel compressed radix-sorting architecture for FPGA that effectively addresses the exponential histogram growth and data skew issues inherent in high-precision sorting. By employing a tree-based recursive circuit with optimized merge, fractal swap, and fractal filter algorithms, the design guarantees bounded memory usage and eliminates the traditional need for data bucketing and pre-processing. Consequently, FractalSort achieves unprecedented bandwidth efficiency and sorting speeds, outperforming state-of-the-art CPU, GPU, and FPGA algorithms by up to 6, 3, and 2.5, respectively, across massive datasets ranging from 4GB to 2TB Recently, Ala’anzy et al.28 proposed GPU-based parallelization of merge sort, quicksort, bubble sort, radix top-k selection sort, and slow sort. The experiments demonstrate that radix sort implemented on GPUs achieves a speedup of approximately 50 on 10 million random data. Additionally, quicksort, merge sort, bubble sort, and slow sort exhibit speedups of 97, 103, 17, and 18.6, respectively. OpenMP OpenMP1 is an Application Programming Interface (API) designed to support multi-platform shared memory multiprocessing programming in C, C++, and Fortran. It provides a portable, scalable model that gives programmers a simple and flexible interface for developing parallel applications. OpenMP is crucial for parallelizing code in shared memory systems, which is essential for optimizing the performance of parallel sorting algorithms. Various OpenMP scheduling types, such as static and dynamic scheduling, can be employed to manage the distribution of tasks among threads efficiently. In this paper, we utilize OpenMP to parallelize the block-based partitioning and sorting processes using OpenMP for and OpenMP task directives. Moreover, we implement OpenMP scheduling to control the data which is partitioned in parallel. Dual-Deque Merge algorithm In this paper, Parallel N-Deque Partitioning algorithm which uses block-based concept is implemented to our sorting algorithm. After parallel partitioning is completed within each block, the partitioned data must be relocated to their correct positions. Note that, data elements less than the pivot are moved to its left, while those greater than the pivot are moved to its right. Therefore, a merging algorithm is integrated into the sorting algorithm to ensure correct data arrangement. The Dual-Deque Merge algorithm18 is employed to merge data based on the boundaries of a dual-deque. The concept of this algorithm is shown in Algorithm 1. Dual-Deque Merge algorithm. It begins with sort the dual-deque data structures using their boundaries (Lines 1-2, Algorithm 1). Next, the boudnaries in both deqg and deql are popped. Note that, the boundaries in deqg and deql are popped from the front, and back, respectively (Lines 4-5, Algorithm 1). The left boundary of deqg and right boundary of deql are assigned to ii and jj, respectively (Lines 6-7, Algorithm 1). The data in arr[ii] and arr[jj] are exchanged until ii or jj is out of bound of that block. Then, ii is increased and jj is decreased (Lines 8-12, Algorithm 1). When the ii or jj is out of bound, the other is pushed back to its deque (Lines 13-20, Algorithm 1). This process is run until ii is not less than jj (Line 21, Algorithm 1). This algorithm is implemented in our Parallel N-Deque Partition Dual-Deque Merge String Sorting algorithm. It is used to merge the data after the partitioning algorithm is executed. The concept of our proposed algorithm is shown in the next section. Parallel N-Deque partition dual-deque merge string sorting algorithm Dual-Deque Merge algorithm. ParallelNPDMSTRPartition. CompareStr. The previous section presented related parallel sorting algorithms. Additionally, the Dual-Deque merge algorithm, which is integrated into our sorting algorithm, was described. The primary objective of this study is to propose an optimized parallel N-Deque partition dual-deque merge string sorting algorithm. This proposed approach integrates PivotSelection, N-Deque partitioning, Dual-Deque merge, and sequential sorting techniques to enhance overall performance and efficiency. The PivotSelection function is employed to select an appropriate pivot element. Five randomly selected data points are extracted from our subarray, and the middle data point is subsequently chosen as the pivot (Line 5, Algorithm 2). The N-Deque Partitioning algorithm (Line 6, Algorithm 2) is our proposed parallel partitioning algorithm, which utilizes the N-Deque data structure to store the left and right boundaries of each block. This parallel partitioning algorithm returns the new pivot position (), which is used to partition at the next level. This algorithm is called to partition the data from L to -1 positions using (Lines 7-8, Algorithm 2). Moreover, the data from +1 to R positions are partitioned using (Lines 9-10, Algorithm 2). Our proposed Parallel NPDMSTRSort is executed recursively to partition the data until its size is less than the sorting cutoff size C. (Lines 1-3, Algorithm 2). N-Deque partitioning algorithm N-Deque data structure is implemented to push/store the boundaries and pop new boundaries of data for partitioning. The number of deques can be set when parallel partitioning is executed. This algorithm begins by exchanging the pivot (arr[p]) at its position (p) and data in the leftmost position (arr[L]) (Line 1, Algorithm 3). It is illustrated in Fig. 1 (Lines 1-7). Next, N-Deque data structures NDeq[T] are allocated to store the boundaries of blocks where T is the number of deques as shown in Fig. 1 (Lines 3-6) (Line 3, Algorithm 3). Then, two deques, deql and deqg in Fig. 1 (Lines 8-9), are created to store the boundaries of values less than or equal to the pivot an greater than the pivot, respectively, (Line 3, algorithm 3). Moreover, the N-Deque Partitioning algorithm with directive is executed to partition the blocks of data in parallel (Lines 4-5,Algorithm 3). In each block, the boundaries are popped from NDeq[t] in the critical section (Lines 7-8, Algorithm 3), where t is the thread number of the N-Deque. After that, the Lomuto’s partitioning algorithm is executed using the boundaries from the N-deque (Lines 10-16, Algorithm 3). Note that, CompareStr (Algorithm 4) is used to compare strings in this algorithm. When that block is partitioned, the boundaries of that block are pushed to the dual-deque deql and deqg in the critical section (Lines 20-21, Algorithm 3). Next, Dual-Deque Merge algorithm18 (Line 28, Algorithm 3) is the sequential algorithm which merges the data that is less than or equal to the pivot and larger than the pivot using a dual-deque data structure. It returns dltemp and dgtemp, which are the left and rightmost unpartitioned positions, respectively. Finally, sequential sorting algorithm (Line 25, Algorithm 3) is the sequential algorithm which is executed when the size of data is less than Cutoff size. This algorithm partitions the data from dltemp.L to dgtemp.R and returns the new pivot position. In addition, the pivot is exchanged to the correct position and returns to its position. Dual-Deque Merge algorithm is illustrated in Fig. 1 (Lines 8-13). Parallel N-Deque partitioning and dual-deque merge algorithm. Block size and sorting cutoff size NPDMSTRSort is a parallel block-based sorting algorithm. It partitions the data in each block using an N-deque data structure. Therefore, we can declare different block sizes of the ParallelNPDMSTRPartition algorithm. Block size (BSz) is a very important parameter in the parallel partition part. This algorithm executes BlockInit() to initialize boundaries to the deques (Line 3, Algorithm 3). Only left and right boundaries, which are equal to Block size, are assigned and pushed to NDeq[T]. When the block size is larger, the number of data in parallel partitioning is larger than the lower block size. Sorting cutoff size (C) is the parameter which is compared to the partition size (Line 1, Algorithm 2). If C is greater than that partition, sequential sorting algorithm is executed in parallel using (Lines 2-3, Algorithm 2). Otherwise, the N-Deque Partitioning algorithm is executed repeatedly. When C is larger, the sequential sorting algorithm will sort the large size of data. The choice of C is empirical and serves as a heuristic to balance the trade-off between parallel throughput and sequential execution efficiency. Block size and sorting cutoff size can affect the run time of the parallel sorting algorithm. OpenMP scheduling in parallel partitioning algorithm OpenMP scheduling is an important feature which can schedule the data in directive. In this paper, each workload of data is popped from N-deque as the boundaries to partition the data. NDeq[T] are interleaved when executed in . OpenMP scheduling can be implemented to control the blocks which are selected to partition. There are several types of OpenMP scheduling, for example, static and dynamic. These two types of scheduling are implemented to schedule the data which pop from the deque. Moreover, chunk size of scheduling can be set during execution. This method affects the number of blocks which are popped from the N-deque when the parallel partitioning algorithm is executed. We can illustrate the concept of OpenMP scheduling in our N-Deque Partitioning algorithm in Fig. 2a–d. The illustration of static scheduling in ParallelNPDMSTRPartition with different CHKSz. Figure 2a shows the static scheduling in ParallelNPDMSTRPartition without declaring CHKSz. This scheduling type divides the block of data that closes each other equally and assigns them to each thread. ParallelNPDMSTRPartition, which uses static scheduling with CHKSz = 1, is shown in Fig. 2b. When CHKSz = 1, the block of data is interleaved among all threads. Figure 2c illustrates static scheduling with CHKSz = 2 in ParallelNPDMSTRPartition. The double block of data is assigned to threads in this CHKSz. Static scheduling with CHKSz = 4 of ParallelNPDMSTRPartition is shown in Fig. 2d. It assigns four blocks that close each other to each thread. Note that, the number of chunks which are assigned to each thread in dynamic scheduling is similar to static scheduling. However, it assigns the work to each thread at run time. Parallel string sorting algorithm This parallel sorting algorithm uses the divide and conquer concept, which consists of a parallel partitioning algorithm and calls the parallel sorting algorithm recursively. Lomuto’s partitioning algorithm is run in ParallelNPDMSTRPartition (Lines 11-15, Algorithm 3). It compares the arr[i] and pivot p. If arr[i] is less than or equal to p, arr[i] is swapped to arr[index], which used to divide the less than or equal to pivot data and greater ones. In this paper, a string sorting algorithm is implemented to Parallel N-Deque Partition Dual Deque Merge Sorting algorithm. CompareStr function is a string compare function, which implements strcmp in to compare str1 and its pivot str2 as shown in Algorithm 4. The result of comparison will be returned to the partitioning algorithm (Line 12, Algorithm 3). Its complexity depends on the string length. Complexity analysis This section presents a time and complexity analysis. The time complexity of NPDMSTRSort is analyzed, assuming that all processor cores (p) are 100% utilization. Note that there are a number of threads T p. This analysis can be divided into two parts: N-Deque Partitioning with dual-deque merge, and parallel string sorting algorithms. Lemma 1 Let N be the size of string data arr, where arr = arr[0], arr[1], arr[2], ..., . Then, the time complexity of N-deque partitioning and dual-deque merge algorithms with p cores is O(). Proof At the beginning, the average number of string comparisons with length L in N-Deque Partitioning with p cores is . The average number of swappings in the dual-deque merge algorithm with a single thread is . Hence, the time complexity in the first level is . In the second level, it contains two independent partitions. The average string comparison with length L in N-Deque Partition with p cores is the same as the first level. Its time complexity is . In the dual-deque merge algorithm, two threads can be executed on both independent partitions. The average number of swappings in the dual-deque merge algorithm in this level is . Therefore, the time complexity of the second level is . In this paper, the Apple M2 processor, which consists of 8 cores, is used to run in this experiment. The average number of swappings in the dual-deque merge algorithm from level 2 is . The N-Deque Partitioning and dual-deque merge algorithms are recursively run until their sorting cutoff C (Line 1, Algorithm 2). Based on the divide and conquer concept, the number of recursive partitioning is levels on average with respect to C. Therefore, the total complexity of the N-Deque Partitioning and dual-deque merge algorithms is As a result, the time complexity of N-Deque Partitioning and dual-deque merge algorithms is O(). Lemma 2 Let p cores perform std::sort() to sort L length string and average comparison is . Each partition of size C in parallel is sorted using omptask directive. Since there are at least partitions, the time complexity of parallel string sorting algorithm is Proof From parallel string sorting algorithm, at least partitions can be obtained. Each partition of up to C data is sorted by std::sort in parallel using p cores. The time complexity of parallel string sorting algorithm is . Theorem 1 The total time complexity of sorting N data with parallel NPDMSTRSort on p cores with sorting cutoff size = C is . Proof Both complexities of N-Deque Partitioning with dual-deque merge (see Lemma 1), and parallel string sorting algorithms (see Lemma 2) are O(), and , respectively. Therefore, the time complexity of NPDMSTRSort is . the total complexity of the N-Deque Partitioning and The space complexity of NPDMSTRSort is analyzed in this paper. This analysis can be divided into two parts: N-Deque Partitioning with dual-deque merge, and parallel string sorting algorithms. Lemma 3 Let N be the size of string data arr, where arr = arr[0], arr[1], , ..., . Then, total space complexity of N-Deque partitioning and dual-deque merge algorithms is = . Proof In the first partition, the array of data is allocated by , where k is the key and value size. Moreover, they have two pointers which reference both values. The space complexity of this array is bytes. Next, the parallel N-Deque Partitioning algorithm is executed. The N-Deque data structure is allocated, which is equal to the number of threads (T). Moreover, the boundaries which have only two data of each block are stored in the N-Deque. While the N-Deque partitioning algorithm is executed, there are N/BSz elements in the N-Deque. The complexity of the N-Deque is up to in bytes. When the dual-deque merge algorithm is executed, two deques are allocated which store the two boundaries data of each block. The complexity of the dual-deque merge algorithm is in bytes. Total space complexity of N-Deque partitioning and dual-deque merge algorithms is = bytes. Theorem 2 The total time complexity of sorting N data with parallel NPDMSTRSort on T threads with sorting cutoff size = C is . Proof The N-Deque partitioning and dual-deque merge algorithms are executed until that subarray is less than C. The parallel string sorting algorithm is executed on that C subarray. The std::sort is executed in parallel to sort using T threads. The space complexity of the parallel string sorting algorithm is . The total space complexity, which consists of array (), N-deque in partitioning algorithm, and dual-deque in dual-deque merge algorithm (), sorting execution (), is + +. Therefore, the total space complexity is . Results This section shows experimental setup, run time, speedup, efficiency, impact of N-Deque on computational efficiency, and impact of OpenMP scheduling on performance. Experimental setup In this paper, several parallel algorithms, ParallelNPDMSTRSort, BQSort, MWSort, TBBSort, LCP-Mergesort, AkibaRadixSort, and std::sort are run on an Apple Mac Mini, which consists of an 8-core M2 processor with 128 kB L1 Cache, 16 MB L2 Cache, and 8 MB Last Level Cache, and 16 GB main memory running on macOS Sequoia. Additionally, these algorithms are run on a 16-core Intel Xeon Gold 6142 processor, 64 GB main memory running on an Ubuntu 24.04 system. The data sizes of 5, 10, 20, and 50 million generated by gensort are processed using these sorting algorithms. Random, and nearly sorted distributions are run on all sorting algorithms. Note that, these data contain three columns. The first column is key, which has a length of 10. The subsequent two columns are value1 and value2, respectively. Each contain two strings. The length of value1 is 32, while the length of value2 is 52. The block size of our NPDMSTRSort is 1/64, 1/32, 1/16, 1/8, and 1/4 times the L1 cache size of the M2 processor. Additionally, sorting cutoff sizes are 1/4, 1/2, 1, and 2 times the L1 cache size. The OpenMP scheduling algorithms are set to default, static, and dynamic with chunk sizes set to default, 1, 2, and 4. Finally, Number of deques are 1, 2, 4, 8, and 16. The experimental setup is presented in Table 1. Table 1Setup of the experiments (M: million, CSz: Cache size).ParameterValueSorting AlgorithmNPDMSTRSort, BQSort, MWSort, TBBSort,LCP-MergeSort, AkibaRadixSort, std::sortDistributionRandom, Nearly SortedData Size N2M, 5M, 10M, 20M, 50MBlock Size BSz ()1/64, 1/32, 1/16,1/8, 1/4Cutoff Size C ()1/4, 1/2, 1, 2OpenMP Schedulingdefault, static, dynamicScheduling Chunk sizedefault, 1, 2, 4Number of deques1, 2, 4, 8, 16 Setup of the experiments (M: million, CSz: Cache size). In addition, Apple Instruments application, and Perf profiling tools are used to measure the metrics which affect these parallel sorting algorithms on Apple M2 machine, and Intel Xeon Gold machine, respectively. This can be used to optimize the parallel sorting algorithm. Run time, speedup, and efficiency NPDMSTRSort uses a block-based concept to partition the data. The block size value affects its run time. Table 2 shows NPDMSTRSort with Block size = {1/64, 1/32, 1/16, 1/8, and 1/4} CSz. Table 2Run time in seconds of our NPDMSTRSort (8 deques) sorting random and nearly sorted distributions in each data size and Block size CSz at Cutoff size = 1 CSz (Alg.: Algorithm, Dist.: Distribution, Block size: BSz, Million: M, RD: Random, NS: Nearly Sorted).MachineAlg.Dist.RDNSN2M5M10M20M50M2M5M10M20M50MBSzApple M2NPDMSTR1/640.160.270.430.832.280.140.160.360.521.501/320.150.260.430.852.260.140.170.300.551.481/160.120.250.430.842.260.140.200.350.541.541/80.230.250.430.832.250.140.170.350.611.561/40.150.260.440.832.270.150.140.340.581.55BQSort0.260.501.042.215.930.180.350.721.524.23MWSort0.110.190.390.802.350.110.200.430.862.56TBBSort0.120.310.611.333.550.120.310.611.333.55LCP-MergeSort0.080.200.420.974.440.080.200.400.884.15AkibaRadixSort0.020.040.090.200.650.020.040.080.170.58std::sort0.510.992.074.3011.420.310.350.751.584.42Xeon 6142NPDMSTR1/640.160.270.320.541.230.160.180.200.350.811/320.160.260.310.581.190.170.180.200.320.821/160.220.260.310.561.210.170.180.200.380.901/80.240.260.350.561.250.180.190.210.390.871/40.270.260.330.571.240.170.190.230.390.85BQSort0.050.100.200.411.040.040.070.130.270.68MWSort0.060.130.250.521.340.050.100.230.461.09TBBSort0.080.170.340.691.680.050.100.200.421.06LCP-MergeSort0.230.571.102.205.660.230.561.072.115.22AkibaRadixSort0.070.160.370.852.290.050.120.230.461.18std::sort0.450.992.074.3011.420.300.731.343.319.16 Run time in seconds of our NPDMSTRSort (8 deques) sorting random and nearly sorted distributions in each data size and Block size CSz at Cutoff size = 1 CSz (Alg.: Algorithm, Dist.: Distribution, Block size: BSz, Million: M, RD: Random, NS: Nearly Sorted). The best run time values of NPDMSTRSort on Apple M2 machines for sorting random data of sizes 2, 5, 10, 20, and 50 million are 0.12, 0.25, 0.43, 0.83, and 2.25 seconds, respectively. It is observed that the run time of NPDMSTRSort while sorting random 50 million data is smaller compared to BQSort, MWSort, TBBSort, LCP-MergeSort, and std::sort. However, it is slightly greater than MWSort when sorting 2, 5, 10, and 20 million data. Our NPDMSTRSort algorithm exhibits superior performance in sorting larger datasets compared to MWSort. The best run time values for NPDMSTRSort on Apple M2 machine, for nearly sorted data of sizes 2, 5, 10, 20, and 50 million are 0.14, 0.14, 0.30, 0.52, and 1.48 seconds, respectively. It can be noticed that the run time of NPDMSTRSort sorting nearly sorted 50 million data is less than BQSort, MWSort, TBBSort, LCP-MergeSort, and std::sort. Additionally, the run time of NPDMSTRSort exceeds that of AkibaRadixSort when sorting random and nearly sorted data on an Apple M2 machine. It is evident that the runtime of NPDMSTRSort when sorting random data is comparable to the runtime of the nearly sorted algorithm when dealing with smaller data. Conversely, when the data size increases, the runtime of NPDMSTRSort sorting random data surpasses that of the nearly sorted algorithm. The optimal run time values of NPDMSTRSort on an Intel Xeon Gold 6142 machine for sorting random data of sizes 2, 5, 10, 20, and 50 million are 0.16, 0.26, 0.31, 0.54, and 1.19 seconds, respectively. Its run time when sorting random 50 million data is less than the MWSort, TBBSort, LCP-MergeSort, and std::sort. The best run time values for NPDMSTRSort on Intel Xeon Gold 6142 machine, for nearly sorted data of sizes 2, 5, 10, 20, and 50 million are 0.16, 0.18, 0.20, 0.32, and 0.81 seconds, respectively. Note that, our NPDMSTRSort’s run time values are only greater than BQSort. The experimental results demonstrate a significant performance flip between two architectures. While AkibaRadixSort maintains an edge on the Apple M2, NPDMSTRSort consistently outperforms it on the Intel Xeon Gold 6142. This performance divergence highlights the critical role of memory subsystem design in the scalability of parallel sorting. On the Intel Xeon Gold 6142, the superiority of NPDMSTRSort and standard libraries like BQSort, and MWSort over AkibaRadixSort suggests a bottleneck related to the Memory Wall and the complexities of Non-Uniform Memory Access (NUMA). Moreover, it can be noticed that the best run-time value corresponds to BSz values of 1/64 and 1/32. The block size parameter is the primary focus in the experiments. The run-time of NPDMSTRSort reveals slight variations across different block sizes. NPDMSTRSort uses the divide and conquer concept to partition data and then sort the data sequentially when that partition is small enough. The algorithm can be optimized by its cutoff size to improve its performance. Table 3 presents the run time of NPDMSTRSort with cutoff size = {1/4, 1/2, 1, 2} CSz. Table 3Run time in seconds of NPDMSTRSort (8 deques) sorting random, and nearly sorted distributions in each data size and cutoff size at block size = 1/8 (Alg.: Algorithm, Dist.: Distribution, Block size: BSz, Cutoff size: C, Million: M, RD: Random, NS: Nearly Sorted).MachineAlg.Dist.RDNSC1/41/2121/41/212NApple M2NPDMSTR2M0.110.160.150.350.070.070.140.205M0.250.260.250.270.180.150.170.3310M0.470.430.430.430.350.330.350.2920M0.850.970.830.850.560.540.610.6450M2.322.262.252.271.531.611.561.63Xeon 6142NPDMSTR2M0.090.130.220.450.090.130.220.455M0.150.170.260.460.180.150.170.3310M0.260.280.310.490.350.330.350.2920M0.470.490.570.640.560.540.610.6450M1.171.211.402.271.531.611.561.63 Run time in seconds of NPDMSTRSort (8 deques) sorting random, and nearly sorted distributions in each data size and cutoff size at block size = 1/8 (Alg.: Algorithm, Dist.: Distribution, Block size: BSz, Cutoff size: C, Million: M, RD: Random, NS: Nearly Sorted). The best run time values for NPDMSTRSort on Apple M2 machine, for random data of sizes 2, 5, 10, 20, and 50 million data, are 0.11, 0.25, 0.43, 0.83, and 2.25 seconds, respectively. The optimal runtime is achieved at a data size of 2 million. However, when the value of C is increased, the run time is significantly increased. This can be attributed to the fact that the std::sort is called during the initial partitioning algorithm. The minimum run time for sorting random data is at CSz when the data are larger. It can be observed that when C is small, the run time exceeds CSz. On the other hand, if C is greater than 1 CSz, the run time increases. The best run time values of NPDMSTRSort sorting nearly sorted data of sizes 5, 10, 20, and 50 million are 0.15, 0.33, 0.54, and 1.53 seconds, respectively. The minimum run time for sorting nearly sorted data from 5 to 20 million is at C = 1/2 CSz. However, if the data is increased to 50 million, the best run time is at C = 1 CSz. The optimal runtime values for NPDMSTRSort on an Intel Xeon Gold 6142 machine, utilizing random data of varying sizes (2, 5, 10, 20, and 50 million), are as follows: 0.09, 0.15, 0.26, 0.47, and 1.17, respectively. We can observe that as the value of C increases, the runtime significantly increases. The small C is appropriate for our NPDMSTRSort algorithm. Speedup and Efficiency are the metrics which can be used to measure the performance of the parallel algorithm. Speedup can be defined by the run time of sequential/parallel algorithm as shown in Equation 1. Note that, the speedup of the parallel sorting algorithm presented in this paper is calculated as the ratio of the std::sort algorithm’s runtime to the parallel sorting algorithm’s runtime (). Efficiency is used to measure the performance of the algorithm. It can be calculated by Speedup per processor core as shown in Equation 2. Best speedup of this algorithm is up to 5.23 at Data size = 20 million data with Block size = 1/64 and Cutoff size = 1. Table 4 presents Speedup and Efficiency of sorting algorithms at Data size = 20M. Table 4Speedup of NPDMSTRSort (8 deques) sorting any distribution compared to other sorting algorithms for each block size and cutoff size at data size = 20 million on Apple M2 (Dist.: Distribution, Block size: BSz, Cutoff size: C, Million: M, RD: Random, NS: Nearly Sorted).AlgorithmDist.CBsz1/641/321/161/81/4NPDMSTRRD1/45.185.104.775.085.201/24.934.875.184.445.1115.235.085.155.185.1925.025.225.035.085.20NS1/42.543.043.002.842.971/23.033.003.032.932.9113.052.882.912.572.7322.532.472.382.442.48BQSortRD-1.95NS-1.03MWSortRD-5.37NS-1.83 Speedup of NPDMSTRSort (8 deques) sorting any distribution compared to other sorting algorithms for each block size and cutoff size at data size = 20 million on Apple M2 (Dist.: Distribution, Block size: BSz, Cutoff size: C, Million: M, RD: Random, NS: Nearly Sorted). The benchmark speedup attained by BQSort, MWSort, on Apple M2 machine when sorting random data is up to 1.95, 5.37, respectively. Conversely, the speedup of NPDMSTRSort sorting random data is up to 5.23 at BSz = 1/64 and C = 1 CSz. It can be observed that the speedup of NPDMSTRSort sorting 20 million data is superior to BQSort. Nevertheless, the speedup of NPDMSTRSort is slightly inferior to MWSort. The speedup of BQSort and MWSort sorting nearly sorted data is up to 1.03 and 1.83, respectively. On the other hand, a speedup of 3.05 can be achieved when BSz = 1/64 and C = 1 CSz. It is evident that this experiment exhibits a direct correlation with the results presented in Tables 2 through 3. The sorting cutoff size is calibrated to correspond to the cache of the processor. Impact of N-Queue on computational efficiency The N-Deque data structure is implemented to store the boundaries of the partitioning algorithm for the NPDMSTRSort algorithm. N-Deque data structure varies between 1, 2, 4, 8, and 16. Number of deques affects the number of threads in the parallel partitioning algorithm. If there is only one deque, all of the blocks of data will be stored in that deque. Otherwise, blocks of data will be scattered to the others. Table 5 shows the speedup of NPDMSTRSort for each N-Deque at Block size = 1/64 and Cutoff size = 1 on Apple M2 and Intel Xeon Gold 6142 processors. Table 5Speedup of NPDMSTRSort for each N-Deque and data size at block size = 1/64 and cutoff size = 1 (Alg.: Algorithm, Dist.: Distribution, Million: M, RD: Random, NS: Nearly Sorted).MachineDist. N 124816Apple M2RD2M3.093.223.333.242.525M3.603.783.883.883.8010M4.014.394.714.814.6220M4.194.855.205.234.3050M4.234.584.895.011.74NS2M0.442.212.232.241.825M2.082.191.902.311.3710M2.212.372.512.101.6420M2.672.852.843.052.8150M2.472.572.742.952.55Xeon 6142RD2M2.342.442.642.742.765M3.534.004.354.634.7710M4.896.307.388.208.3420M5.757.588.799.689.7750M7.229.3910.6811.4511.58NS2M2.122.162.182.201.785M4.224.453.874.702.7910M3.954.244.483.752.9320M5.615.995.976.405.9150M5.115.325.676.115.28 Speedup of NPDMSTRSort for each N-Deque and data size at block size = 1/64 and cutoff size = 1 (Alg.: Algorithm, Dist.: Distribution, Million: M, RD: Random, NS: Nearly Sorted). Speedup of 5.23 is achieved while sorting random 20 million data at 8 deques. It is evident that an increase in the number of deques leads to a corresponding enhancement in speedup. NPDMSTRSort is executed on an Apple M2 processor with an 8-core architecture in this experiment. Consequently, speedup values are diminished when the number of deques exceeds 8. It is noteworthy that the speedup of NPDMSTRSort when sorting 50 million data using 16 deques is 1.74, primarily due to memory constraints. A speedup of 3.05 is obtained while sorting nearly sorted 20 million data at 8 deques. The speedup is slightly increased, similar to the speedup of NPDMSTRSort when sorting random data. Consequently, the optimal speedup of NPDMSTRSort is attained when N-Deque is 8. On the other hand, the best speedup of Intel Xeon Gold 6142 is up to 11.58 at N-Deque is 16. It can be noticed that the N-deque value is equal to the number of CPU cores. The optimal performance is directly proportional to the number of processor cores. A speedup of 6.40 can be achieved using N-Deque when sorting nearly sorted data. When sorting random data, the speedups of NPDMSTRSort are greater than those achieved when sorting nearly sorted data. This is likely due to the fact that most of the data in the nearly sorted distribution is already in the correct partition, allowing the std::sort algorithm to perform efficiently. Impact of OpenMP scheduling on performance In the previous section, we introduced OpenMP Scheduling feature which has several types. Static and dynamic scheduling are customized and optimized with their chunk size. Table 6 shows Speedup of NPDMSTRSort for each type and its chunk size where Block size = 1/64 and Cutoff size = 1/4. Table 6Speedup of NPDMSTRSort for each scheduling type and chunk size at Block size = 1/64, Cutoff size = 1/4, and N-Deque = 8 (Sched: OpenMP Scheduling algorithm, Dist.: Distribution, CHKSz: Chunk size, Million: M, RD: Random, NS: Nearly Sorted).MachineDist. N Sched defaultstaticdynamic-124124Apple M2RD5M3.733.933.903.863.933.853.8410M4.054.544.823.864.814.314.8420M5.175.254.934.845.225.135.2450M5.045.044.985.085.064.965.03NS5M1.362.652.762.792.832.782.8110M1.772.972.992.992.612.951.9320M2.542.803.053.042.213.023.0650M2.892.952.902.882.852.652.92Xeon 6142RD5M7.997.827.807.865.665.615.4710M9.949.549.609.556.966.977.0120M10.7510.6810.7110.687.557.467.5850M11.9211.7611.7411.747.737.607.64NS5M2.776.705.625.675.765.755.7210M3.177.435.345.344.655.273.4520M5.339.216.416.394.646.366.4450M5.9810.716.015.965.895.496.05 Speedup of NPDMSTRSort for each scheduling type and chunk size at Block size = 1/64, Cutoff size = 1/4, and N-Deque = 8 (Sched: OpenMP Scheduling algorithm, Dist.: Distribution, CHKSz: Chunk size, Million: M, RD: Random, NS: Nearly Sorted). The best speedup of NPDMSTRSort sorting random data on an Apple M2 machine is up to 5.25 at data size = 20M. Note that, speedup of NPDMSTRSort at data size = 50M is decreased due to out-of-main-memory. It can be observed that the best speedup of NPDMSTRSort is at data size = 20M, with static scheduling and chunk size = 1. This can be due to the chunk size being fitted to the cache memory of the processor. A speedup of 3.06 is achieved when sorting nearly sorted 20 million data using dynamic scheduling with a chunk size of 4. However, this scheduling method and its chunk size exhibit instability in the case of small data sizes. In contrast, the NPDMSTRSort algorithm demonstrates greater stability when employing static scheduling with a chunk size of 2. The overhead of dynamic scheduling in the parallel sorting algorithm is greater than that of static scheduling. Conversely, the optimal speedup of 11.92 can be achieved on Intel Xeon Gold 6142 at a data size of 50M using default scheduling when sorting random data. Moreover, a speedup of 10.71 can be achieved when sorting nearly sorted data at N = 50M using static scheduling with a chunk size of 1. The disparity in performance between this machine and the Apple M2 may be attributed to the larger cache size of this machine. The data size is more suitable for the cache compared to static or dynamic scheduling with fixed chunk sizes. Figure 3a–c present branch load misses and cache misses for each value of N in the NPDMSTRSort algorithm, configured with 4 deques, a block size of 1/64, and a cutoff size of 1 on an Apple M2 machine. BQSort is a parallel algorithm that employs a concept similar to NPDMSTRSort. It is a suitable comparative algorithm to our NPDMSTRSort. Most of the branch load misses values of NPDMSTRSort when sorting random data are less than BQSort. BQSort employs a block-based concept to partition data and merge them concurrently. At each level of partitioning, branch load misses increase due to the compare-and-swap algorithm employed in parallel block-based partitioning. Furthermore, this metric increases when data are merged at the conclusion of the partitioning algorithm. Additionally, cache misses for NPDMSTRSort are slightly higher than those for BQSort. Branch load misses have a more substantial impact on parallel sorting algorithms compared to cache misses. On the other hand, MWSort employs the mergesort algorithm, which divides data and merges them using a multi-way merge technique. Due to this, it cannot be directly compared to these values to MWSort. In this algorithm, its cache misses and branch load misses grow linearly and are greater than the others are caused by the auxiliary array. Most of the branch load misses and cache misses values of NPDMSTRSort are less than MWSort. However, when sorting the largest data, cache misses of NPDMSTRSort are greater than MWSort. Consequently, the performance of NPDMSTRSort is similar to MWSort. Branch load misses and cache misses of NPDMSTRSort, BQSort, MWSort sorting random data at 4 deques, Blocksize = 1/64, and Cutoff size = 1. To enhance the performance of sorting algorithms, it is crucial to minimize both branch load misses and cache misses. These two values impact the efficiency of algorithms that employ the same concept. Table 7 shows speedup, processor cores, and its efficiency of several parallel string algorithms9. It can be observed that a speedup of 5.25 can be achieved on Apple M2. Additionally, its E value is 0.65, which is slightly lower than MWSort but higher than BQSort on this machine. Furthermore, the E value of our NPDMSTRSort algorithm can reach up to 0.74 on Intel Xeon Gold 6142 processors. This value surpasses that of MWSort, Parallel Radix Sort, and Parallel Multikey Quicksort algorithms. Table 7Best speedup and efficiency of NPDMSTRSort with other parallel string sorting algorithm implementations.AlgorithmsSpeedupProcessor coresENPDMSTRSort_M25.2580.65NPDMSTRSort_Xeon11.92160.74BQSort_M21.9580.24MWSort_M25.3780.67BQSort_Xeon13.57160.85MWSort_Xeon8.37160.52Parallel 26.88320.84Parallel Radix Sort16.00320.50Parallel Multikey Quicksort11.84320.37 Best speedup and efficiency of NPDMSTRSort with other parallel string sorting algorithm implementations. It can be noticed that the speedup of parallel , radix sort, and multikey quicksort are up to 26.88, 16.00, and 11.84 on a 32-core processor. The time complexity of parallel is O(). Furthermore, it can utilize the processor more efficiently than the others. Therefore, its E of parallel is up to 0.84. Next, parallel radix sort is a well-known parallel string sorting algorithm. Its E is up to 0.50. Conclusion In this paper, we propose an optimized parallel N-Deque partition dual-deque merge string sorting algorithm. This algorithm integrates N-Deque partitioning, dual-deque merge, and sequential sorting techniques to enhance performance and efficiency. Speedup and efficiency are the metrics used to measure the performance of the parallel algorithm. The optimal speedup of NPDMSTRSort can reach up to 5.25 on an 8-core Apple M2 machine with a data size of 20 million. The parameters of NPDMSTRSort include B = 1/64, which is the smallest value of B. The sorting cutoff C is set to 1. The number of N-Deques is equal to the number of cores. OpenMP scheduling is configured as static scheduling with a chunk size of 1. Block size, cutoff size, number of deques, and OpenMP scheduling are the parameters that significantly affect the performance of the algorithm. Despite the significant performance gains achieved by the proposed algorithm on multi-core processors, several open research challenges remain. A critical gap in the current literature is the adaptation of complex partition and merge techniques for heterogeneous computing environments, such as GPU-accelerated architectures or distributed computing clusters, which are essential for handling extreme-scale datasets. For future work, we aim to further minimize the memory footprint by investigating a block-based two-way iterative scanning approach. Instead of maintaining auxiliary deques, this method would process data blocks from both the leftmost and rightmost boundaries, converging toward the center of the array. This would transition the algorithm toward a truly in-place partitioning mechanism, effectively reducing the auxiliary space complexity to near-constant overhead. Finally, we plan to evolve the current static cutoff into an adaptive hybrid selection framework on heterogeneous systems. This would enable the algorithm to dynamically select the most efficient sorting kernel based on specific data characteristics, such as the Longest Common Prefix (LCP) depth and alphabet distribution. Author contributions The idea of the algorithm is from all authors. A. R. developed the source code of sorting algorithm. A. R. prepared all tables and figures. S. K. wrote the manuscript in English. The experiments are run and tested by all authors. All authors discussed the results. The manuscript is reviewed by all authors. Funding Apisit Rattanatranurak received funding from Faculty of Applied Science, King Mongkut’s University of Technology North Bangkok. Data availability In this paper, we use datasets which are generated by gensort. This generator during the current study are available in https://www.ordinal.com/gensort.html or request from the corresponding author. Code availability The parallel N-Deque Partition Dual-Deque Merge String Sorting algorithm source code is available in https://github.com/apisitr-collab/NPDMSTRSort. Declarations Competing interests The authors declare no competing interests. Footnotes Publisher’s note Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations. Contributor Information Sirilak Ketchaya, Email: sirilak.ke@ssru.ac.th. Apisit Rattanatranurak, Email: apisit.r@sci.kmutnb.ac.th. References Associated Data Data Availability Statement In this paper, we use datasets which are generated by gensort. This generator during the current study are available in https://www.ordinal.com/gensort.html or request from the corresponding author. The parallel N-Deque Partition Dual-Deque Merge String Sorting algorithm source code is available in https://github.com/apisitr-collab/NPDMSTRSort.