2015/08/31 by Richard Cole, Vijaya Ramachandran
Computer Science · #Algorithms and Data Compression #Computer network #Computer science #Machine Learning and Algorithms #Optimization and Search Problems #Programming language #Resource (disambiguation) #Sorting #cs.DC #cs.DS
paper · pdf · doi:10.1145/3040221
published as ACM Transactions on Parallel Computing (TOPC), Vol. 3, No. 4, Article 23, 2017 · A version very similar to this appears in ACM Transactions on Parallel Computing (TOPC), Vol. 3, No. 4, Article 23, 2017. The current version adds some additional citations to earlier sorting algorithms, and a comparison to Sharesort
openalex publication_date 2017/03/23 · arxiv created 2017/11/02 · arxiv updated 2017/11/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/06
We present a deterministic sorting algorithm, Sample, Partition, and Merge Sort (SPMS), that interleaves the partitioning of a sample sort with merging. Sequentially, it sorts n elements in O ( n log n ) time cache-obliviously with an optimal number of cache misses. The parallel complexity (or critical path length) of the algorithm is O (log n log log n ), which improves on previous bounds for deterministic sample sort. The algorithm also has low false sharing costs. When scheduled by a work-stealing scheduler in a multicore computing environment with a global shared memory and p cores, each having a cache of size M organized in blocks of size B , the costs of the additional cache misses and false sharing misses due to this parallel execution are bounded by the cost of O ( S · M / B ) and O ( S · B ) cache misses, respectively, where S is the number of steals performed during the execution. Finally, SPMS is resource oblivious in that the dependence on machine parameters appear only in the analysis of its performance and not within the algorithm itself.