Parallel Sorting Algorithms for Multicore Systems Using OpenMP

Abstract

Sorting is a core primitive in scientific computing, databases, information retrieval, and systems software. With the ubiquity of multicore CPUs, parallel sorting is now essential for meeting latency and throughput requirements at scale. This manuscript presents OpenMP-based designs of four representative sorting families—comparison sorts (parallel quicksort and mergesort), a data-parallel network sort (bitonic sort), and a non-comparison method (LSD radix sort)—and evaluates them under realistic workload and architecture constraints. We articulate algorithm–architecture co-design choices including partition concurrency, task granularity, memory layout, NUMA placement, branch predictability, and synchronization costs.

A rigorous methodology specifies datasets (uniform, nearly-sorted, and skewed distributions), input sizes, compiler flags, and OpenMP schedules (static/dynamic/guided) with thread affinity and first-touch allocation. Statistical analysis uses 30 independent repetitions per condition to estimate speedup, scalability, and effect sizes, and to compare the impact of schedule policy. On a 16-core x86-64 system, an OpenMP task-based quicksort attains the best time-to-solution on uniform 32-bit integer keys for large arrays, with mergesort close behind; a cache-aware LSD radix sort shows high single-thread performance but limited scaling due to memory bandwidth pressure; bitonic sort serves as a predictable, branch-free baseline with competitive scaling but a higher constant factor. The discussion synthesizes design guidelines for choosing and tuning OpenMP constructs—loops, tasks, and reductions—so that practitioners can map algorithmic parallelism to shared-memory hardware effectively.