Optimized N-deque partition dual-deque merge string sorting algorithm
Sirilak Ketchaya, Apisit Rattanatranurak · 2026
Read Optimized N-deque partition dual-deque merge string sorting algorithm by Sirilak Ketchaya, Apisit Rattanatranurak (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/PMC13265812.txt.
Description
Sirilak Ketchaya and Apisit Rattanatranurak present a 2026 computing paper on sorting huge lists of text strings in parallel. String sorting underpins tasks from genome work to database indexing, but its scattered memory access wastes processor caches. Their algorithm splits data into blocks, sorts blocks independently with a multi-deque method, then merges the results.
They tested the method against leading parallel sorters on two machines, an eight-core Apple M2 and a sixteen-core Intel server chip. Speedups reached more than five times on the Apple chip and nearly twelve times on the Intel chip over single-thread runs. Sorting twenty and fifty million random strings kept parallel efficiency at about two thirds and three quarters. Settings like block size, deque count, and scheduling style all shifted performance through cache misses and branch errors. The authors map those trade-offs for users.
Catalog record
| CREATOR | Sirilak Ketchaya, Apisit Rattanatranurak |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 52511 |
| LICENSE | https://creativecommons.org/licenses/by/4.0 |
| RIGHTS | CC BY |
| SOURCE | Europe PMC |