P3Sort：耐心排序新突破，现代处理器上的高效合并与排序算法

"《耐心是一种美德：重新审视现代处理器上的合并与排序》(PatienceisaVirtue:RevisitingMergeandSortonModernProcessors)是Badrish Chandramouli和Jonathan Goldstein合著的一篇深入研究论文。随着数据中心中大量基于日志的数据涌现，对近乎有序数据集进行排序的需求日益增长。本文主要关注在主内存中高效排序和合并数据的问题。 论文的核心内容围绕着一种经典但被遗忘的排序算法——耐心排序(Patience Sort)展开。该算法分为两个阶段：创建已排序的子序列（称为“run”）和将这些子序列合并。作者指出，通过对原有耐心排序算法进行关键改进，特别是在合并有序子序列（即合并runs）的技术上，如引入新的“ping-pong merge”方法，可以使其在随机和近乎有序数据的排序任务中与当前最佳的基于比较的排序技术相媲美，甚至有时表现得更优。 ping-pong merge是一种创新性策略，它在主内存中高效地合并有序runs，通过利用现代处理器的特性，如缓存优化和流水线并行性，显著提升了合并过程的速度。此外，作者还提出了一种新型排序技术P3Sort（基于ping-pong patience和排序的组合），这种技术结合了算法和架构的革新，使得排序性能达到了一个全新的高度。 这篇论文不仅重新评估了排序和合并的基本原理，而且展示了如何通过巧妙的设计和对现代硬件的理解，将传统算法提升到一个竞争性的新水平，对于理解和优化现代数据中心中的数据处理工作具有重要意义。"